Could you do it in 2 phases? First, everyone selects a random partner and exchanges their random number. Each pair then has a result that is locked in. Then everyone submits their result to be summed up as already suggested (Pos/neg = heads/tails).
If there are an uneven number of players, then one player makes a three-some.