Trite one-liners aside, I think you'll find in practice that some good teams rebase commits on feature branches all the time in order to keep the commit history readable. The implicit contract in that case is that nobody else considers that branch to be usable until it's merged.
It all comes down to the definition of publicity. If your team considers a feature branch to be privately owned by the requestor except for the purposes of code review, it works great.
I do not mind feature branch rebasing, when it does not violate the publicity rule (let's call it that). After the history is public, rewriting history is such a dangerous endeavor as to be completely inadvisable. More so, if one is actually looking at the end goal: a linear repository history. I can't even understand the need for a (fake) linear repository history.
If a feature branch is under development for a year, and then merged in.... you wind up with commits in master that only appeared today, but are dated (and appear in the commit history timeline) up to a year ago. It's actually a different kind of 'rewriting history', really.
This can be very confusing when trying to figure out what happened. And even worse when trying to figure out where a bug was introduced (via git bisect or manually).
Still, I, like you, try to avoid rebase history rewrites whenever possible, because they can lead to such messes. But I've come to understand why people want them, it's not just "aesthetically pleasing commit history", which sounds kind of inane I agree.
Then "only when it's not public" rule effectively means "never do it" for most people's development practices. Anything that takes longer than an hour or so for me to do is going to be in a public repo, for the 'backup' nature of making sure i don't lose it while in progress if nothing else. Anything that more than one person collaborates on (or you want code review suggestions on) obviously is going to be in a public repo. It's pretty rare feature branch work I do that never makes it into a public repo (before it's committed to master).
