A less powerful solution implemented completely locally: A "known_hosts" file for SSL certificates for repeat visits. As long as you've visited a site once before, any subsequent visits will be safe.
To deal with certificate upgrades, certificate Y could present a signed verification that it obsoletes a past certificate X. Then, when a client that trusts certificate X receives certificate Y, it can update its "known_hosts" file accordingly. This change would require more than just local changes, but remote cooperation.
As long as your first visit wasn't compromised.
Sites like Google's also don't use the same certificate every time. Out of my own curiosity I scraped their SSL sites for a while, I saw tens, maybe hundreds of different certificates being presented. There's no way of telling which are actually Google's.
But then there's no way of telling which postal mail is actually from Google, right? :)
If all paths (including those through Tor) lead through a piece of compromised infrastructure (a rogue access-point like a pineapple, or subverted router) both will report that the site uses the same certificate despite the MITM.