Part of your question on the "history" of a coin toss is based on the idea that that 'fairness' - which is generally defined as a lack of bias in an instrument to produce certain results instead of others - is particularly difficult, and you might need to go to great (if not impossible) lengths to produce true fairness.
As the article linked above notes, it is actually remarkably difficult (and for some definitions even impossible) to truly bias a coin. You don't need a uniform surface, a pure elemental metal, or a homogeneous and flat distribution of atoms - a malformed lumpy coin will do.
Slam it down, hit it with a hammer, cover it with any matter or weird marks, impart it with all the history you care to. So long as you don't let the coin bounce as part of your experimental throw, or use a particular 'unfair' coin throwing strategy (like throwing the coin so it never actually flips in the air), you'll end up with a fair coin regardless.
The reason for this is at the heart of what probability means, and in most definitions this is directly a notion of uncertainty. It is not a question of "heads or tails", but rather "it's going to be either heads or tails, and both are equally likely, but we won't know which it is until it has happened".
Experimentally because it turns out that coins are remarkably hard (and with good procedure, all but impossible) to bias, early mathematicians (and sophisticated gamblers) were able to both theoretically and experimentally address notions of uncertainty, probability, risk, likelihood, and the whole field that would later become statistics.
But underneath it all is trying to deal with uncertainty: there is something we don't know. Note that this does not require - or imply - absolute and intractable uncertainty, that we cannot learn more and thus improve our prediction (possibly to 100% accuracy). It just means that given a certain state of incomplete knowledge, we know some things and not others, and some things can be inferred and others cannot.
The notion of 'fairness' is given as an assumption in some mathematical contexts, but in more sophisticated or in-depth treatments of various areas of statistics such a notion is done away with. Indeed, if something is not fair it will - by definition - not behave the same way as an unfair coin, and many techniques of statistics are an attempt to deal with this. A whole mess load of statistical experimental techniques are aimed at attempting to determine whether or not a coin is indeed fair!
Playing with assumptions is at the heart of many statistical methods. If we assume the coin is fair, then we assume certain results are quite typical and others are so unbelievably rare that if we encountered them we would tend to reject the idea of fairness. A coin tossed a 1000 times that always comes up heads, for instance, is theoretically still a possible result of a fair coin! It's just so weird a result that we can comfortably reject the idea of fairness - even though we have not 100% proven anything. This is the basis for "null hypothesis testing", which is quite a useful little tool. One can never insist one knows anything for certain, but we can at least know when the odds are in our favor.
In the end, you don't need a magical randomness box that is impossible to predict. You just need uncertainty. And this is the true cause of the gambler's fallacy: an incorrect belief that you know something useful about predicting the future, when it turns out you just don't. It turns out we humans have a lot of intuitions about how to deal with uncertainty that are off, too. If you are interested in these classes of errors I strongly recommend the books "Against the Gods: The Amazing History of Risk" and "Predictably Irrational", which offer absolutely dozens of other examples about how our intuitive approaches to risk, uncertainty, and probability are weird, mistaken, or just plain wrong.
