git filter-branch --tree-filter 'rpl -iR oldstring newstring *' HEAD
will do the job. If this branch tracks a remote, then untrack it,
git remote rm origin rm -rf .git/refs/original
Now this is a freestanding branch which can be pushed to a new remote. Note that everyone who cloned from an existing remote that has been replaced will need to discard their files and clone again, because all the IDs for the entire history will have changed. Also it appears that newstring has to be non-empty; I tried "" but it doesn't work in filter-branch because rpl wants to query the user to make sure it's OK to replace with an empty string.