How to explain this paradox involving coin-tosses? I do this experiment:
I flip fair coin, if it comes heads on first toss I win.
If it comes tails, I flip it two times more and if both heads I win.
Else, I flip it 3 more times, if it comes heads all three I win.
On the n'th turn I flip it n times, and if I get n heads I win and quit the game.

Before I start, I calculate probability I win at some point: 1/2+1/2^2+1/2^3... = 1.
So I am guaranteed to win this game always.

However I started to play, and it came tails first toss, now I calculate probability I win 1/2^2+1/2^3+1/2^4...=1/2.

Before I start I was guaranteed to win, but now only 50% chance I will win? What went wrong with the mathematical reasoning?
You are wrong about your probability of winning at the beginning.

Let $p_n$ be the probability that you have not won by stage $n$.

Then the probability that you have will not have won at stage $n+1$ is $p_n(1-(\frac{1}{2})^{n+1})$.

So the probability that you never win is $\prod_{n=1}^\infty (1-(\frac{1}{2})^n)$.  This is not zero.

Specifically, this is $\phi(\frac{1}{2})$ where $\phi$ is the Euler function.

In particular, $$\log(\phi(\frac{1}{2}))=-\sum_{n=1}^\infty \frac{1}{n}\frac{1}{2^n-1}$$

which converges.
What went wrong with your reasoning? 

"Before I start..." is not the same as "now (i.e. AFTER you have started)"!