In reality, 'rewriting history' comes down to things like:
* Creating a commit, then amending the commit message.
* Rebasing all of your current changes on top of a new version of master (basically re-applying all of your commits/patches on top of master).
* Fixing a typo creating a commit, and then squashing that into the original commit.
(Note: That these operations all happen on topic branches prior to being merged into master. Once you merge into master, or just publish for public consumption, then you should not be rewriting history at all.)
From my perspective, the view that git is useless because the ability to rewrite history means that valuable information is being lost is an extreme overreaction by people without much (or any) git experience.
If you want to hold this view, you should have rational examples of workflows where people will lose valuable information just as a matter of course.
However, that history can still be very useful: You might hit a variation on those bugs later, and seeing the original unrewritten history can help a lot in refreshing your memory on what you did there (and it can be even more helpful for someone else getting up to speed on the code trying to fix that bug). Losing the history after history rewriting isn't a good thing.
With your MQ workflow, you can only ever do this for your own patches.
But git branches also have pain points. The only way to save history from before you rewrite history is to save branches, as you mentioned - but doing that manually every time you rewrite history is a pain.