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.