1) Deprecate insecure HTTP. Literally get all the browsers to agree on a deadline X years out and then drop support for it entirely. HSTS would become irrelevant. I hold little hope of this ever happening, even in a HTTP/2 world. See IPv6
2) Keep increasing the size of the trusted, preloaded list of HTTPS enabled sites shipping with browsers: Neither the implementation nor the process to manage the list scales. It's just crappy all-round.
3) Standardise some SRV records for web protocols in the DNS so browsers can efficiently determine what is supported: Requires DNSSEC to prevent downgrade attacks.
Of these, #3 seems to me to be most practical. With regard to DNSSEC issues I would give these counterpoints:
* DNSSEC could and should be augmented to support ECC, obliterating the concerns with regard to large records and weak RSA key lengths.
* Browsers (or your OS's dnscache process) can cache DNS responses from most of the chain. If the ZSK hasn't been rolled over for a particular domain then I don't see the need to reverify it again on each request. It's not like revocation really works in HTTPS today anyway, so you probably aren't going to bother to check upstream for NSEC records on each request. Or just recheck upstream once a day. I don't really know, but I'm sure these latency issues can be minimized. Googles obsession with latency is how we ended up with the barf that is HTTP/2 rather than something that actually improves websec in the first place.
Another thing I don't often see people mention about HSKP and HSTS, regardless of whether they can be used as "supercookies", is that they create a more-or-less permanent shadow browser history on your machine. This alone is borderline show-stopper afaiac
Since DNSSEC can't decisively fix HTTPS downgrade, why bother deploying it?
I addressed your ECC point in the followup to my post:
http://sockpuppet.org/stuff/dnssec-qa.html
Adam Langley seems to agree; he said "it won't happen within 10 years".
I think the centralised CA model really needs to be replaced, although it will be hard to displace as long as those involved have a financial interest in continuing it.
We lack the proper tools to make this safe.
I haven't looked into HPKP much, but it appears it has the ability to be configured in a "report only" mode if name your header "Public-Key-Pins-Report-Only". This will allow you to test your implementation to make sure it's correct before renaming the header to start enforcing.
The idea of a non-enforcing mode for testing purposes also exists in DKIM (though DKIM didn't really catch on much due to servers with proper DKIM configurations getting compromised and sending spam...)
I would say that HSTS is far more dangerous as I don't see a similar "testing" mode available.
edit: It would be a good idea to make sure your max-age setting doesn't exceed the expiration date of your intermediate certificate, so don't go crazy with it. A tool with built-in safeguards to handle most of this configuration would be welcome.
I meant tools to prevent you from making the mistakes in the first place, not for fixing it after the mistake.
The non-enforcing mode doesn't help. When I talk about mistakes, I mean things like losing access to your cert or timing mistakes in rolling the cert. If I roll it out today, it will be fine today. It will probably fail at some point in the future though, and fail hard, unless I follow very strict processes.
HSTS is considerably less dangerous. Once it's set up, it will continue to work without you having to do anything extra. HPKP on the other hand requires you to actively consider when you generate new certs, and when you add extra HPKP headers to your responses, and when you roll the certs etc.
I can change my CA or generate a new key today on a whim, because I don't do HPKP. If I did do HPKP, this would require considerable thought and preparation in advance.