One of the proposed solutions to this problem is the idea of certificate notaries. Unlike a CA, notaries would not be unique. The idea was proposed by Moxie Marlinspike, who has the distinction of having the most awesome name of any security researcher.
Unlike a CA, a notary doesn't sign the certificate, but rather validates it. Users, rather than site operators, choose notaries that they trust. The notary then checks whether the certificate that a site is offering is one that it expects.
There are several ways that this might work. The proposed standard is to try reaching the site from multiple locations on the Internet, to see whether you get the same certificate. This makes man-in-the-middle attacks more difficult, because it means that you need to attack multiple possible paths. If a server is in France and you see the same certificate when you connect to it from Australia and from the U.S., this doesn't necessarily mean that the connection is secure, but it does mean that there isn't an attacker on your local network. (It's still possible that there's an attacker in France.)
One possible additional check is whether the certificate has changed recently. The exact criteria that the notaries use isn't specified. A notary may require any criteria it chooses.
More importantly, the idea of notaries is that you can place different levels of trust on different notaries. Not all sites require an equal level of trust. You don't need to trust your online blog account as much as you need to trust your bank account, for example. For certain domains, you may want to require stricter notaries, multiple notaries, or both; for others, a single attestation may be enough.
The key selling point of this idea is what Marlinspike describes as "trust agility." This means that it's easy for the end user to revise his or her trust rules. Unfortunately, this is also a weakness of the system, due to one implementation detail that's difficult to work around: user apathy. When DigiNotar was compromised, it was relatively easy for the browser makers to push an update that removed DigiNotar's signing certificate. Persuading all users that they need to remove a bad notary is going to be harder.
DNSSEC for Key Distribution
An alternative security model is to use DNSSEC to replace the whole of the public key infrastructure. DNSSEC is now used for most top-level domains, although getting it supported for the rest of the tree is taking a while.
With DNS, every layer in the DNS hierarchy signs the layer below. Most people are familiar with DNS for resolving host names, but really DNS is a distributed typed key-value database. There are DNS record types for things like telephone numbers and geolocation coordinates as well as host names. One DNS record type is already defined for storing IPSec keys. With an IPSec key, you can establish an end-to-end secure connection at the IP layer, so any TCP traffic is already encrypted.
The downside of this approach is that it introduces a single point of failure. Everyone has to trust the root DNS zone. Everyone also has the various registrars that the servers use. On the plus side, everyone has to trust these entities anyway; even with perfect encryption, you're still relying on DNS to get the host name.
The certificate notary idea reduces this level of trust slightly, because it means that you can refuse to trust sites if their IP address changes too frequently, for example, or if different sites see different DNS results (although this would break some content-distribution networks).
In the end, encryption is not one but two hard problems. The mathematics behind various encryption algorithms are often nontrivial to follow, but they're fairly well audited. The mechanisms behind trust are much harder, partially because trust relies strongly on a psychological element, which is difficult to quantify.
The certificate notary idea is an interesting start, but it still doesn't address the user side of the equation: How do you decide who and what you trust online?