I have the impression there's a general confusion between probability theory and statistics. The two are of course related, but not identical. Basically, statistics is about existing data, while probability is about prediction. The connection is that if the number of repetitions of a random experiment goes to infinity, the statistics is expected (not guaranteed!) to converge against the probability. That is, if you've assigned the probabilities correctly, the probability that the statistics deviates from the prediction from probability theory goes to zero in the limit of infinite experiments (note however that the probability that you get an exact agreement between probability and statistics goes to zero!). And due to that connection, if we have sufficient statistics, we take the statistics results as probabilities for further predictions, assuming that the statistics closely agrees with the probabilities, because provided that we are not missing any important influence on or regularity of the outcome, it is unlikely that the sufficient statistics deviates significantly from the actual probability.
Now let's look at the example from the question. The coin in question is supposed to be a fair coin. Nevertheless it is assumed that the coin has produced only heads for millions of years. I'll assume it has been tossed frequently during that time (because otherwise, a coin that is thrown once every ten million years and produced heads three times in a row would also fit that description).
So the statistics says that the coin showed 100% heads for very many tosses. There's nothing wrong with that statistics, it tells us the facts.
Based on that statistics, people made a model that this coin is not a fair coin, but actually is a coin that almost certainly produces heads on each toss. If we take as two competing models the model of the coin as a fair one, and the model of a coin as a head-producing one, probability theory tells us that the second one is much more likely to be true than the first one. Note that it doesn't tell us that the second one is true. It just tells us that we most likely get better prediction with that assumption. And for millions of years that was actually true for this coin.
Now that coin suddenly starts to produce tails. And not just one or two, but a thousand in a row. Now, this doesn't invalidate the statistics. The tosses before still are 100% heads. And even including those 1000 heads, the statistics is still damn near at 100% heads. So the heads-only model still works better than the fair coin model. However, the most likely explanation ion that case would be that something affecting the coin changed (although nobody knows what did change), and thus the probabilities of the coin after the change are not the same as the probabilities before. Note that the fair coin assumption still isn't ruled out (it even got slightly less improbable), but it's still very unlikely (because also 1000 tails in a row are a very improbable event for a fair coin).
And BTW, even if the inhabitants of that world were wrong with their model of the coin, for their purposes the wrong model was better than the correct one for millions of years, because during that time their wrong model actually made the correct predictions. Indeed, given that fact, one may actually question whether their model really was "wrong".