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:
Stout, Quentin F.; Warren, Bette;
Tree algorithms for unbiased coin tossing with a biased coin,
Ann. Probab. 12 (1984), no. 1, 212–222.
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.
Ryabko, Boris Ya.; Matchikina, Elena;
Fast and efficient construction of an unbiased random sequence,
IEEE Trans. Inform. Theory 46 (2000), no. 3, 1090–1093.
Näslund, Mats; Russell, Alexander;
Extraction of optimally unbiased bits from a biased source, IEEE Trans. Inform. Theory 46 (2000), no. 3, 1093–1103.
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.
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.