You can even rewrite a branch shared between developers that hasn't been merged mainline: once it's done, have one of the developers create a duplicate branch in their own private namespace, and rebase and merge that.
Accidents happen, though. If you want to be guaranteed safety, enforce that every developer have their own remote fork. They can rebase at-will on their own fork, and submit pull requests to the mainline repository. (If you're using GitHub, this is dead simple, since you can open pull requests across forks.) This method introduces a fair bit of hassle and overhead for a smallish team, though.
Alternatively, if you use github, you can set access controls on forks to read-only and send pull requests from your fork to the main repo.
Your teammates don't care much if you do the former. From their perspective, it's the same as if you'd committed at different points in your development process. So long as your final, rewritten history doesn't violate your team's preferences as to the granularity of commits, you're fine.
So go ahead and rewrite your local, un-pushed changes if you feel it makes the history more organized.
But if you do the latter--rewriting history that has been pushed--you're in trouble. All developers should be able to assume that the history in the central repo is immutable. Most likely, they will rely on that assumption.