Have you ever looked at the powerful git filter-branch command? It offers, amongst many features, the ability to maintain history while re-writing the tree to a subset of its past self. A common use case is to prune out a large and unnecessary folder of binaries that was never intended to be under version control.
The filter-branch command can be very confusing at first. What's needed is a set of working examples. I've got 5 scripted flows to show you how to use it. Just hop over to my ever-growing git workbook that I use for workshops and look for module #27 as PDF or as HTML. There's a corresponding set of samples in the example-repos directory.
If you are interested in more of these type of advanced moves with Git, stay tuned for my upcoming O'Reilly Git Master Class videos (directly O'Reilly link soon), monthly Git trainings via GitHub.com, No Fluff Just Stuff tour stops, or one of my international conferences hosting my Git talks.