It's not as if rebase is commonly used. It's there for those rare instances when you, say, remove a file that it turns out you don't have the copyright for and need to purge it completely, or that huge binary file some newb (ok, it was me) committed a while back that's not needed and makes cloning take 10 minutes.
Fossil looks really exciting to me- I've used git a ton and like it but don't really delude myself into thinking it can't be disrupted. But, seriously, you're missing a critical feature; instead of trying to patronize your would-be future users by defensively stating that it's a "good thing and we're proud of this missing functionality"- you could simply state something along the lines of "In general we think not having the equivalent of rebase is a good thing, but should you seriously need something like it, this is opensource and we'd love for you to contribute..." etc.
[Edit: I'm referring to git-filter-branch etc. to remove those things, not the rebase command per se, but in context of the original page's "Immutable==good" argument I interchanged the two]