This is an old post, but I am very surprised that no answer so far points out the exact issue, i.e. the exact mistake in the alleged contradiction (although @Deusovi's answer maybe does so, implicitly).
OP writes:
For example imagine a series of coin tosses where the coin comes up heads a million times. The [refutation of the] Gambler's fallacy says that the chance for the next toss to be tails is still 1/2. However the law of large numbers says, that since enough repetitions of tosses have come up heads, the next toss is more likely to be tails. (Which is definitely wrong?)
Indeed the sentence in boldface is wrong. That is not what the law of large numbers says! (It is, rather, exactly what the gambler's fallacy falsely believes.) What the law of large numbers says is that if you look at a very long sequences of coin tosses, and you assume that it is a fair coin, then on average, we expect half of them to be heads and half of them tails.
That means that if your first million tosses all gave heads, you have two options:
Option A) Still assume it is a fair coin, and keep tossing. Then the law of large numbers says that the next million coin tosses should roughly be half heads, half tails, so after that (but still counting your first million heads), starting with your rock solid faith in the coin being fair, you are now most reasonable in expecting to see a ratio of about $$\dfrac{1'500'000 \text{ heads}}{2'000'000 \text{ tosses}} \text{ versus } \dfrac{500'000 \text{ tails}}{2'000'000 \text{ tosses}},$$ i.e. a ratio of $75\% : 25\%$. If you toss ten million more times after your initial million heads, LLN tells you to expect $$\dfrac{6'000'000 \text{ heads}}{11'000'000 \text{ tosses}} \text{ versus } \dfrac{5'000'000 \text{ tails}}{11'000'000 \text{ tosses}},$$ i.e. a ratio of $\approx 54.5\% : 45.5\%$. If you toss a billion times more after your initial million heads, LLN tells you to expect $$\dfrac{501'000'000 \text{ heads}}{1'001'000'000 \text{ tosses}} \text{ versus } \dfrac{500'000'000 \text{ tails}}{1'001'000'000 \text{ tosses}},$$ i.e. a ratio of $\approx 50.05\% : 49.95\%$.
What we observe here is called regression to the mean, and here is a post where the top comment and answer say the same as what I want to say with the above. The Law of Large Numbers makes no statement about the probability of "the next" coin toss. If it makes a statement at all (by the way, one can doubt that meta-mathematically, cf. 1, 2, and note how I tried to word things carefully above in "based on assumption of fair coin ... most reasonable to expect ..."), then it makes a statement about the average of all tosses. Vaguely said, the fact that the ratio (here) goes to 50:50 is not due to the numerator on the right "catching up, with more tails now", but due to the denominator getting bigger, and the longer sequence eventually making the first million quite negligible.
Option B) Scrap the assumption that the coin is far. It is a very interesting question how to justify that and to come up with some "better" assumption on the (un)fairness of the coin. (The linked question basically asks the same as what you ask in this paragraph; note how most answers also start by saying we have the two options A and B that I'm talking about here; the answer by user307169 reiterates what I said in option A; the answer by Mark Fischler says how, if you go with option B, you are now faced with a new dichotomy between frequentist and Bayesian approaches; and the answer by Hayden gives what I think is the most appealing Bayesian approach on what to do next in option B.) However, then the Law of Large Numbers simply does not apply any more and thus makes no statement at all (in particular, no statement about what is likely in the next toss).
You see that either way, the law of large numbers does not say what it is claimed to say.
By the way, I personally would go with option B.
