However, each party needs to be sure that the identity of the other is who they expect, I.e. that a MitM is not occurring. Sometimes the best way to achieve that is an out-of-band key exchange
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.