So depending on the application and use case, it may be acceptable to not accept connections on port 80. I still think setting the HSTS header is important, but the redirect isn't (always important).
Redirecting to HTTPS is heavily encouraged by the HSTS spec.[1] Clients are just as easily man-in-the-middled if you refuse connections on port 80. The middleman can connect to your HTTPS and use it to send valid (though maliciously corrupted) HTTP responses to the client.
There's only one way to ensure clients aren't MitM'ed on first connect: Go to https://hstspreload.appspot.com/ and submit your site to Chrome's HSTS preload list. Firefox slurps Chrome's list from time to time. The lists are shipped with browser updates, so the whole process takes months.
