Rewriting from scratch just so you can have automated tests is silly - you have a codebase that (mostly) works, and you probably can test it (just not automatically). A rewrite, even with all the tests in the world, introduces extra risk, and it always takes longer than expected. So don't do that.
Writing tests to achieve 100% coverage in one go is also silly, because it means you are halting on-going development to implement something which doesn't add any value yet. In most situations, this is unacceptable. Further, writing tests for code that already works and doesn't need changing has little benefit other than verifying that it does indeed work (but if it's running in production, you better be pretty sure about that already).
The best way to go, IMO, is to add tests as you go. That is, for every change you make, apply the following steps:
- See whether existing tests sufficiently describe the current functionality.
- If necessary, add tests to capture the current functionality of that particular part / module / class / function / ... Verify that they pass.
- Refactor existing code if necessary.
- Modify the tests to reflect the intended new behavior.
- Modify the code to make the tests pass.
Steps 4 through 6 are just basic TDD; the only addition is that you retroactively add tests as needed before you start the actual TDD cycle.
If you follow this procedure, and the tests you add in step 2 are sufficient, the codebase will gradually move towards full test coverage.
Of course, if you are going to rewrite anyway, for different reasons, then going TDD right from the start is probably a good idea.