This is one of those things that usually garners the response "normal people would never do that", but honestly I'm surprised that no-one has even tried.
Let's say that web browsers put a short hash of the certificate right in the URL bar. Amazon, for example, could print its hash on every shipping box. Banks could print their hashes on plaques in every branch. Newspapers on their, well, newspapers. Media organizations could occasionally add them to their TV logos and radio jingles. And so on. There's any number of out-of-band channels available.
For most sites, you actually wouldn't need to verify the hash anyway. You usually wouldn't care. But when you did care, I honestly think this isn't such a crazy idea.