I have incrementally refactored large codebases by committing to a guide of which constructs to replace with what, what is the final goal and writing test cases. Once the guide was seen beneficial by other developers, rather they were forced to use it, they were surprised how well that worked. All this was behind the scene from the customer and updates bugfixes were going out. Re-write may be the answer sometimes, many times, a well thought incremental re-factoring guide is an easier path.