Mercurial will eventually have history re-writing; I say this as an outsider who has watched Mercurial slowly catch up to git by adding features that git has already had for a while. They will have to add it sooner or later to remain relevant and competitive.
The article explains why it makes sense to rewrite history - it's so as not to push garbage out on the world. One of the big niceties of distributed, disconnected repositories is that you can muck about, try things out, make mistakes, correct them, clean things up, and then push that out to a public repo. The difference with git is that you don't have to make a separate patch, roll things back (possibly restarting with a clean repo from master), then apply the patch and make a "clean" commit - you simply rebase the commits in git.
When I'm maintaining code, I don't care about every little twiddle of bits that happened; I care about discrete, human-level, bug or feature related patches, and sometimes development in progress doesn't match up with that. Being able to rewrite history means being able to have not just maintainable code, but a coherent change history.
I find the Mercurial way improves codebase hygiene: do your dirty stuff in a clone repository. If you allow rebase, people will mess up and create ugly histories. Mercurial's lack of rebasing is a plus: it's a tool-enforced discipline of working in cloned repository and only bringing clean, compilable, executable code back into the real repository.
As a firm believer in mechanism not policy, I find that Mercurial, much like Python, tries to force its users to the "one true way", which is assumed to be the "best" and "correct" way to do something, when in reality, it's just needlessly constraining. You want to enforce policy? That's entirely possible with git. It's just not turned on by default because not everyone needs it; it's a hammer looking for nails.
And it's perfectly possible to mess up and create ugly histories without rebase; that's exactly one of the prime use cases for rebase - cleaning up ugly histories. You want me to clone a clean repo from master and try applying pieces of my patch from scratch? Screw that noise! Even with the speed of git clone, I'd much rather pick, squash and rewrite commit messages in rebase.
After having been able to use and appreciate git rebase (and especially git rebase -i) I can say I'll never go to hg if they don't have history rewriting. I'm a big boy, I can make smart decisions, Mr. DVCS.
yeah, history rewriting is something i've never needed - but then i've never had problems branching and merging which i've heard can be 'nightmarish'. i don't think it is, suck it up and get on with it and it takes 2 minutes it just looks scary up front, even before dvcs. fyi i use git at work... it is 'okay', but it has not solved any problems for me over, e.g. svn with a bunch of scripts.
