Let $N$ be the number of flips needed, and let $E(N)$ be the expected number of flips needed. You always need a flip, but with probability $\frac{1}{9}$ you will not make progress and need to "start over" and flip again, with another $E(N)$ expected flips needed to finish. So
$$E(N) = 1 + \frac{1}{9} E(N).$$
Solving for $E(N)$ gives $\color{blue}{E(N) = \displaystyle\frac{9}{8}}$.
Let $p$ be the probability that the coin comes up heads. Suppose that you’ve tossed a head $n$ times. If you play one more time, your expected payoff is $100(n+1)p$; if this is less than the $100n$ that you’ve won so far, you shouldn’t play again. The inequality $100(n+1)p<100n$ boils down to $n(1-p)>p$, or $n>\frac{p}{1-p}$; if $n=\frac{p}{1-p}$, your expected payoff is equal to your current winnings. Thus, if $n\ge\left\lfloor\frac{p}{1-p}\right\rfloor+1$, you should not play again. If $n=\frac{p}{1-p}$, you can play again or not. And if $n<\frac{p}{1-p}$, you should play again. We can get a slightly nicer expression for the cutoff: you should stop when $n$ reaches
$$\left\lfloor\frac{p}{1-p}\right\rfloor+1=\left\lfloor\frac1{1-p}-1\right\rfloor+1=\left\lfloor\frac1{1-p}\right\rfloor\;.$$
For a fair coin, with $p=\frac12$, this says that if $n>1$, you shouldn’t play again: if you toss heads once, you can go ahead and try again or not, as you please, but if you toss heads twice, you should quit. If $p=4/5$, the cutoff is $n>4$: if you’ve managed to toss four heads in a row, you can try again or not, but if you’ve managed five, quit.
To see how this relates to Sam’s calculus-based answer, start with the Maclaurin series for $\ln(1-x)$:
$$\ln p=-\sum_{n\ge 1}\frac{(1-p)^n}n\;,$$
so
$$\frac1{-\ln p}=\frac1{\sum_{n\ge 1}\frac{(1-p)^n}n}=\frac1{1-p}\cdot\frac1{1+\frac12(1-p)+\frac13(1-p)^2+\ldots}\;.$$
Clearly $1<1+\frac12(1-p)+\frac13(1-p)^2+\ldots<\sum_{k\ge 0}(1-p)^k=\frac1p$, so
$$\frac{p}{1-p}<\frac1{-\ln p}<\frac1{1-p}=\frac{p}{1-p}+1\;.$$
Best Answer
I think it depends on knowing the exact bias of the coin. For a simple example, if you know the coin comes up heads exactly one-third of the time (in the long run), then you can flip the coin twice, call it heads if you get heads once, tails if you get tails twice, do-over if you get heads twice. You get a decision 8 times out of 9, leading to a lower number of expected flips than for the von Neumann solution.
EDIT: There's a very nice discussion of the problem, especially the case where you don't know the bias of the coin, at http://www.eecs.harvard.edu/~michaelm/coinflipext.pdf [link updated 19/07/12]
MORE EDIT: There's a fair bit of literature on this problem. Here's a sampling of what's out there:
MR0723740 (85f:60020) Stout, Quentin F.; Warren, Bette; Tree algorithms for unbiased coin tossing with a biased coin, Ann. Probab. 12 (1984), no. 1, 212–222.
MR1763468 (2001f:65009) Juels, Ari; Jakobsson, Markus; Shriver, Elizabeth; Hillyer, Bruce K.; How to turn loaded dice into fair coins, IEEE Trans. Inform. Theory 46 (2000), no. 3, 911–921. 65C10 (94A60)
MR1763481 (2001a:65006) Ryabko, Boris Ya.; Matchikina, Elena; Fast and efficient construction of an unbiased random sequence, IEEE Trans. Inform. Theory 46 (2000), no. 3, 1090–1093. 65C10 (65C05)
MR1763482 (2001d:68177) Näslund, Mats; Russell, Alexander; Extraction of optimally unbiased bits from a biased source, IEEE Trans. Inform. Theory 46 (2000), no. 3, 1093–1103. 68Q99
MR2245123 (2007d:94019) Cicalese, Ferdinando; Gargano, Luisa; Vaccaro, Ugo; A note on approximation of uniform distributions from variable-to-fixed length codes, IEEE Trans. Inform. Theory 52 (2006), no. 8, 3772–3777. 94A29 (94A45)
MR2300366 (2008b:65010) Pae, Sung-il; Loui, Michael C.; Randomizing functions: simulation of a discrete probability distribution using a source of unknown distribution, IEEE Trans. Inform. Theory 52 (2006), no. 11, 4965–4976. 65C10 (68W20)