The thing that is random is the lifetime of any particular radioactive atom or molecule. The decay follows a "distribution", which is an overall pattern, but it doesn't tell you at which particular time a particular atom will decay. It gives you only a probability for each individual atom.
I don't know the answer and I'm sure you could find out with your own research what, if any, theories there were to explain the (apparent) randomness of radio-active decay. My guess is that there was an assumption that once you knew enough about a particular atom, you could determine when it was going to decay. In the same way that you could study a macroscopic process that followed a statistical law. By looking closely enough you could explain the apparent randomness, perhaps by a distribution of initial conditions or the randomness of external influences.
The difference with QM is that it postulated a fundamental randomness (i.e. only probabilities) at the lowest level: probabilities that, according to the theory, could never be explained in terms of a more fundamental deterministic model. That said, the Bohmian interpretation of QM tries to do just that.
The short answer to your question is perhaps simply that everyone thought the probabilities of radioactive decay could eventually be explained by a deterministic theory. It would be interesing to know whether anyone took the randomness at face value and postulated that atoms might decay according to fundamentally probabilistic laws.