Correct. HSTS does not protect against a first visit to a site. And to work around HSTS, there are many ways to get users to clear their caches, install new browsers, or use new devices to browse sites they've already visited.

Technically, if the domain had DNSSEC enabled, it might prevent this kind of attack, but no regular consumer is using a validating stub resolver, so even DNSSEC wouldn't work.

Now that browsers are saying "Not Secure" by default for HTTP pages, users are apparently expected to notice this popping up where it didn't before and realizing they're on a phishing site.

Many sites can be included as HSTS only in Chrome itself, so it wouldn't be entirely useless.

https://hstspreload.org

No. If the domain (and its subdomains) are preloaded - then a first visit is not required. The HSTS requirement is then baked into a list supported by modern browsers such as Firefox and Chrome.

Dynamic pinning (HPKP header) is being rolled back from browsers because of the reasons you mention. Only a small set of static pins will remain (in Chrome, Google sites for example).