Negotiate a secure connection without certificates?
If you have a side channel where you can verify a string is identical you can simply do a Diffi Hellman key exchange and then verify both sides have the same resulting key.
If the side channnel is secure from evesdroppers you can directly compare the key. But you would probably prefer to compare a hash of the key. This also allows comparing something much shorter then the actual key.
For example I have seen systems for voice communication which after setting up the key the parties are expected to read out a verification number, but this simply assumes the mitm can not take the place of both parties and read out a different number to each. With nothing pre shared preventing man in the middle is tricky.
If you have a mitm resistant side channel which is public and very low bandwidth the above solution works. If it is high ebough bandwidth simply do DH key exchange over it.

Edit: to ensure the user can compare a short hash we should add a large random nounce before hashing the key. So a mitm won't be able to make keys which will collide with a truncated hash.