How about: Both players write down a hidden bid, the player with the higher bid takes black, and gives the bid as komi (if the bids are equal, use nigiri to choose color).

How about komi as the average of the two bids, rounded up to the nearest half point?

If the komi lies between two (honest) bids, then each player thinks that they have the advantage.

_________________
Sheik Yerbuti -- if that really is your name --