I've done this when I was submitting patches to a large git based project (perl5). The trick is to to the rebase and then re-tag your old branch. That way the old work is there if you need to reference it. Since it has a real live tag, it will not get garbage collected.
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.
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.
Mercurial Queues are bolted onto Mercurial and you can often see the cracks. Merging is my pet peeve which I've already mentioned. I think it's not controversial to say that it's a pain? I think that, in true Mercurial tradition, there's an extension in development for it now...
So why do we need to deal with this bolt-on and the resulting pain? Because Mercurial branches aren't good enough, or at least can't adequately support the workflow people need. Compare the amount of Mercurial users using mq to the amount of git users using quilt or equivalents.
I don't disagree with the abstract principle of operation of Mercurial Queues. I disagree with Mercurial as it is.
However, if you use git to rewrite the history of your branch as part of your development process, AFAIK there is no way to go back in time and instantly see what your branch looked like at time K in the past, because history has been rewritten.
1) It may be possible to do this with reflog. I don't know for sure because I haven't needed to do this yet. (I think the main problem is that by default reflog purges old history at some point)
2) You can simply create more branches as you go. i.e. replace qcommit by git checkout -b etc. Then push the final ones.