I know there are quite several projects for offline data sending out there, like the carrier pigeon in 2009. Deepak send me recently a link to his let s say straight forward Datagram idea of exchanging data via encrypted  SD-cards in snail mail.  Right now the site looks more like an idea than a working service, but sure would be possible. I would question if you really needed a central service/data base to exchange public keys … but yes, good old anonymous snail mail :-) like it! And back in the days it was very commone to mail hard drives :-)