A thousand times this. For my first year to year and a half of using git, I didn't even know that you could re-write your history. I just started out with a personal repo on my own machine, where I'd init, add, rm, commit, and look at logs. Then I learned how to start working with someone else's repo, which introduced me to cloning, pulling, pushing, fetching, and all that jazz. As the project sizes grew, I realized how useful branches were, so I became more familiar with tracking things upstream, merging, and some more advanced workflows. Finally I started poking around in the git object model, and learning how I can clean up my local history before a push. It was baby steps all the way.

Trying to use rebase the same week or month that you learn git (or version control period), while doable for some, is just crazy for everyone else. You don't jump into riding a bike before you learn to walk.