A Browser-based solution?
Unless I'm overlooking something, browsers distributed outside of China need just two features:
1. A list of domains which can ONLY be accessed via https, not http. If the Great Cannon starts MITMing other domains than Baidu, the next stage would be to apply the https-only rule to all Chinese IPs (or ASes, and someone else suggested.)
2. Remove China's root CA from the list trusted by non-Chinese browsers.
At that point, if Baidu wants traffic from clients outside the PRC, it will need to sign its https responses with a certificate from some other root CA, thus preventing MITM actions by the Great Cannon.
Of course, PRC officials could force Baidu to divulge its non-PRC-signed cert. The rest of us would know that had happened as soon as the Great Cannon resumed spewing: that would be the signal for the browser-makers to refuse to send even HTTPS requests to PRC IPs/ASs, or at least to any domain with which the great cannon interferes.
Google's already non-grata enough with the Chinese that they'd have no reason not to do this in Chrome: I don't know about the Firefox folks. Apple's likely to be a problem: I doubt that Apple would make the OSX and iOS default browsers implement the disclplines suggested above: their business it too tightly bound to the PRC.