It's really not a chicken/egg problem. We solve the easy problem first, then the hard one. I'm not yet sure there's actually a good solution to the cert problem.
There is one solution I can think of, but it involves equating URLs with identities via a Namecoin-like system, and that technology just isn't there yet.
No. It's only chicken and egg because we needlessly conflated two very distinct problems a few decades ago.
Problem 1: isolate the communication between myself and whatever other party is actually sending me a message. Easily solved by encryption. (You're being MITM'd? That sucks. But you have now at least isolated the communication to you and the attacker. The problem domain just shrunk quite a bit.)
Problem 2: verify that the other party is who she claims to be. Not easy to solve but a completely separate problem from Problem 1.
We could solve Problem 1 tomorrow (modulo the time it takes to upgrade every browser/mail client/etc.) by simply encrypting all traffic, period, and not doing any authentication whatsoever. We would then be exactly where we are right now in terms of having a PKI system with all of its advantages and faults, but we would then have the amazing bonus feature of preventing all passive attacks, period.
