
Decide on a random N and what tails (even) and heads (uneven) mean.

Each party generates a random number

Combine the numbers with a conmutative operation of some sort, the harder the operation the better.

Take the hash N times. (Can be done independently by each participant)
(4.5) optional: for extra robustness, do some hardtocalculate transformations to the result of 4. (Can be done independently by each party)
 The final result is either uneven or even === coin toss. (0 will be treathed as even*.*)
This is not infalibe, one party could get all the numbers a precalculate a answer to get a specific result but they will need to randomly try numbers. adding some timing constrains, using big numbers and hard operations would make that sort of attack not really practicable.
Nice question, had fun thinking about it!