But you lie all the time, by that definition! If I write code, make a mistake and press Ctrl+Z before committing that code, I've just "rewritten" my history without my team mates being able to tell.

Your commit history is just a somewhat arbitrary recording of your code at certain points in time that you choose. Rebasing simply makes that less arbitrary, allowing you to document the way your code is built up in a structured way. Rather than having to decide on the spot whenever a certain combination of code is a good candidate for a single, atomic commit, you can make that judgment with the benefit of hindsight.