Encrypt everything, and post your public key on any keyserver you choose. There is very little sensitive information in a public key (though it can tie you socially to another party, in a cryptographically strong manner, for those who are concerned about such things).
But the point is that an out-of-band and secure key transfer isn't required.
An out-of-band key exchange, or OOB verification of messages, would work. You'd start with messages of low criticality.
In Snowden's case, he didn't even identify himself to Poitras until they'd been communicating for some months.
On the other hand, anyone at any time can create a key with any given name on it. Under PGP, trust is generally imbued through keysigning and trust metrics.
Keys are also cheap: two (or more) parties could create keys (or subkeys) they used exclusively for communications between themselves, if they so chose.