An unbiased choice

The players flip the coin and agreed number (eg five times) each. Whoever has the most heads wins. If there is no winner then they continue with pairs of 'sudden death' throws like a penalty shoot out until there is a winner. Even with a heavily biased coin this should yield a winner fairly quickly.
The bias of the coin is irrelevant as it handicaps (or helps) each player the same.

They could of course go straight for sudden death which must be the most efficient method for number of flips, but this feels a little less satisfying.