I think the best pushState fallback is just allowing page reloads. Hashtags are probably just annoying and confusing for the user experience. Besides, there are other very effective ways to improve page load time.
window.location.pathname = new_path;
And you wind up using cookies anyhow to cross-check (ApEx does), because real applications tend to require authorisation as well as application state.
So, to recap:
1. Uglier URLs
2. Cookies anyway.