This excellent question introduces "TOFU" (trust on first use - e.g. SSH storing fingerprints) and "TBFU" (trust before first use, e.g. PKI Certs, WPA pre-shared-keys).
Obviously, TOFU is useless in the face of an already-established MitM adversary (since you end up trusting the attacker by mistake), and "TBFU" requires some kind of pre-establishment which was itself free from MitM to begin with.
Is there a means by which two strangers can upgrade a public, MitM-infected communications channel into a secured one?
For the sake of argument: assume the strangers are two HTTPS web sites (Alice and Bob), both of which have self-signed certificates only, and that the MitM attacker (Mallory) sits between the internet and one (just one) of these servers. e.g. Mallory can pretend to Bob to be Alice, and can pretend to Alice to be Bob.
The only way I can think of right now, involves real-time third parties (which is OK, but fails if the attacker is also able to MitM those as well, such as if Mallory is doing MitM twice [i.e. sits between Alice and the internet, as well as between Bob and the internet]).