The idea of the HSTS header is that the each client visiting the page should locally store the information "until time ([now]+[max-age] seconds), this site should be accessed using HTTPS only". It is intended to foil man-in-the-middle attacks trying to make the client use an unencrypted connection.
So, any server-side attempts to redirect the client to a HTTP version of the page that used to have an unexpired HSTS header are likely to produce a scary warning message to the user. The only way to avoid this (other than waiting for the specified HSTS period to expire) is to delete the stored HSTS information from any client that has visited the site while the HSTS header was in use.
Here are instructions for this procedure for Chrome and Firefox.
Instructions for Chrome
Navigate to: chrome://net-internals/#hsts
Then type the fully-qualified name of your site to the "Query Domain" box, click the Query button and verify that the HSTS information is there. Then type the same name to the "Delete domain security policies" section and click on Delete.
Instructions for Firefox
Close all open tabs, then open the full history window (press Control-Shift-H on Windows/Linux, Command-Shift-H on Macs, or select History -> Show All History from the menu bar if it's visible). Find the site, right-click on it and select Forget About This Site.
If you need a method that could be automated, you could also edit the SiteSecurityServiceState.txt file in the Firefox profile directory when Firefox is not running. The editor you use should use Unix/Linux style line endings. Find the line that begins with
<fully-qualified name of your site>:HSTS and delete it.