You are correct that this is not always possible. It depends upon $p$. For $N$ flips there are $2^N$ sequences, each with a certain probability that you can figure out if you know the probability the coin shows heads using the binomial distribution. To make a fair game, you need to be able to express $\frac 12$ as the sum of some set of these probabilities. In particular, if $p$ is transcendental, you know it is impossible because if it were possible you would have a polynomial equation with $p$ as a root.