The "Filter-Branch" tip was the most helpful tip for me, since I've been there and deleted my whole repo as quickly as possible not knowing other solutions existed.

http://help.github.com/removing-sensitive-data/