I worked in a shop where we played a game called Chino. Everyone started with 3 coins in their left hand. Each transferred 0, 1, 2, or 3 coins to their right hand and extended their closed right hand. Each made a unique guess of the total coins. A correct guess wins the benefit or liberates the guesser from subsequent rounds to determine who had to do the dirty work. Modified for your situation, each would agree to have 0-3 coins when you meet. The total could pass for a pseudo-random number.
I'm not sure what's allowed. Can use current seconds in someone's watch, for example? Or maybe ask some random person to say a random word, and then use the position of the first letter of that word in the alphabet? This sounds like a really fun problem but I'm certain about the rules.
You can count nearby people, cars, windows, cats, dogs, buildings, whatever you agree upon, those things are pretty pseudo-random, only limit is familiar environment, but you can find other alternatives there (number of pens on one's desktop, number of books, etc.).
Rock paper scissors? Since you are both trying to win, and being predictable means losing you'll be as random as you can be.
this is the nerdiest thing I've heard in my life, haha
Are dices allowed?
From sci.math google group post: "How to generate random number sequences (in your head)"...
With the most relevant answer for you being George Marsaglia's:
~~~~~~~~~~~~~~~~
Choose a 2-digit number, say 23, your "seed".
Form a new 2-digit number: the 10's digit plus 6 times the units digit.
The example sequence is 23 --> 20 --> 02 --> 12 --> 13 --> 19 --> 55 --> 35 --> ...
and its period is the order of the multiplier, 6, in the group of residues relatively prime to the modulus, 10. (59 in this case).
The "random digits" are the units digits of the 2-digit numbers, ie, 3,0,2,2,3,9,5,... the sequence mod 10. The arithmetic is simple enough to carry out in your head.
This is an example of my "multiply-with-carry" random number generator, and it seems to provide quite satisfactory sequences mod 2^32 or 2^64 , particularly well suited to the way that modern CPU's do integer arithmetic.
~~~~~~~~~~~~~~~~
source: https://groups.google.com/forum/?hl=en#!msg/sci.math/6BIYd0c...
edit: so with two people, one of you could chose the seed on alternate days based on some other criteria (like the N you already have or the things @nenadg mentioned (nearby people, cars, windows, cats, dogs, buildings, whatever you agree upon, those things are pretty pseudo-random))