I think you should be able to do something like this with

  git filter-branch

This won't be a terribly fun exercise, and could be very painful if your history contains a lot of merges. (should be easier with the cactus/rebase development model)

And of course everyone will have to hard-reset to the new branch.

I should mention I'm far from an expert on this. I've only ever used git filter branch on a handful of commits, and only based on examples provided by kind internet people. I certainly haven't done anything nearly as far-reaching as you're about to embark on.