Determining nonce between unsynced systems
The standard approach is to have the sender pick his nonce (either randomly, or as a counter), and send it with the packet.  The decryptor then knows what nonce to use to decrypt, because it's right there.  Because nonces aren't assumed to be secret, this works.