Simple. Only fix what people complain about. Fix by the standard XP process: refactor til it's easy, then make the change. As for logistical support, tell everyone that you're changing it as fast as any method. On the testing front, start by writing tests to support what should be, regardless of what is. Once there's a consistent way to run white-box testing, your unit tests will fit snuggly into place. If you work by adding tests for what you are about to do, then eventually the remaining untested portions will also be either very stable or very unused. In either case, remove obviously dead code as you get the opportunity.
With time, you'll get to the point where you can start adding some higher-level tests. Perhaps you can even fit a functional test system on the front end. We're using regexes and perl to drive legacy web applications through their paces. It meant some slight modifications to support the testability of the system, but it's cool.
See also the concept of TestPoint and RefactoringLegacyCodeCategoryRefactoring