I went through this very thing when I first started at the company I work at now almost 4 years ago. The company was fairly small, but was in the process of significantly growing (when I was hired, it was about 20-30 people, now it is around 70-80). The software manager, who I had worked with previously and had brought me in, wanted to bring in better processes including test plans, unit tests, continuous integration, common tool base, etc., had just recently started at the company, was overwhelmed with work, and had very little support from above and below. It was bad. There was no QA. There were no dedicated testers. There were no unit tests anywhere. Plus, the company was on the verge of a fairly large increase in the number of projects that needed software support, and had just suffered a fairly catastrophic failure of their core product on a major project (the company would have folded if it was a product company, fortunately as a services oriented company it was able to remain afloat and even profitable over this time).
The way we have approached it has been to incrementally improve things over time. I would say there were very few wide sweeping changes done.Little by little, we added personnel (a dedicated tester was added right away, a QA manager 2 years ago, and a senior tester one year ago). Little by little, we improved processes (added a Development Guidelines and Practices wiki-page to outline how we do our work right away. Created a development environment setup procedure. Slowly and continuously developed build, installation, and deployment procedures. Maintained design documents by adding a little to them each week, etc.).
On the development front, we started using Bugzilla, adding it to the core work flow - you did not write any lines of code without a bug (either issue or enhancement) being in place first. The code base was spread across Java, Matlab, Embedded Linux applications, drivers, and kernel c and c++ code, as well as custom firmware originally developed by a 3rd party contractor in c. A re-write would be impossible, and like the original poster, there would be no way to meet deadlines if we were to do it. We put in place a release process, and integration test plans for the core products. We also started to better utilize shared code between projects, adding a "common" pacakge for Java code that is built into every application, and a shared repository for both the embedded firmware and Linux source to share algorithms and processes between them.
Our approach on improving the code quality was 3 fold:
1) Brought in unit-test frameworks for all software components. C-Unit for embedded c, TestNG and UISpec4J for Java, slowly built up unit test firmware binaries for the custom firmware code. Note that this was done over the first 2 years, not all at once. The embedded firmware was core to our company, so we started there. Any new code developed would always have unit tests created for it. If we had to fix bugs, a unit test would be created to re-create it before fixing it.
2) For old code, we slowly cleaned it up. It was simply a mess, especially the embedded firmware. It was basically a giant pile of monolithic code with no concept of modularization or testability. Our approach here was to slowly evolve the code into a better design. If we found a bug, as noted above, we would add a unit test for it first. When we fixed that bug, we would spend an additional 2-3 times the amount of time fixing the area of code affected, both design and implementation. Slowly, the code became more modularized, more robust, and much easier to work in. We can add features in half the time it used to take, with far less bugs and much less
3) Any new application were done right from the beginning - incremental releases, unit test coverage, test plans, etc. It was a slow process improving what already existed, but new projects. Developers who were not onboard with this were phased out, with new developers hired to replace them.
I would say it probably wasn't until about 2 years of going through this that we had the majority of the code on the good side of quality, and after 4 years, we are not entirely there. We are in the process of bringing another one of our software products into the fold that has been somewhat rogue (it is run by the science group, so you can understand why!). Basically, the process has been ongoing, at times slow, but very rewardiing, both for me professionally but also for the company financially.