I haven't had a need to do this, but I suppose you could print out an ASCII-armored PGP message and snail-mail it to somebody. Of course this still requires each of you has a computer, just not necessarily an internet connection.