[yason]

You could draw long/short straws to generate bits but since the challenge limited the tools to mortal bodies any other guessing game would do.

One could put his hands behind his back with one hand palm open and the other hand in a fist. The other one then guesses which hand is open and him being right or wrong generates either a 1 or 0. Repeat N times for an N-bit binary number. Both players can influence their choice equally and also equally make assumptions about the other player's intentions when making their own choice.