Many things affect the most appropriate path. A further one you haven't mentioned is timescale. Generally refactoring can be accomplished more quickly than rewriting.

In your case it looks like a true rewrite is not possible in any case. Your only real decision is how deep to cut in the process of refactoring your existing code - you have to keep the system going.

Whatever you do, one of the first things you need is to implement a regression test system to ensure you don't introduce unexpected behaviour during alterations.

If you need to restructure your database, I'd be inclined to split the database back end off as soon as possible, wrap it up in a fairly abstract interface, then work on it as a seperate entity. Again, make sure you write test code to check things don't get broken along the way.

Actually, I'd imagine the whole process will turn into: Identify an area of code, write a test suite for it, put it behind an interface, work on it in stages until happy. To the extent that it is possible, putting stuff behind an interface is a pretty light weight operation and isolates clients of the code from changes behind the interface. It also makes for easy and comprehensive testing.

Note that there are two levels of testing involved here. High level testing of the integrated code - tests written against the code as it is at the moment, and tests written against focused sections of the code when those sections come under the spot light for refactoring.

So, your first task is to write a big test suite for the application, then identify sections of code that can be put behind interfaces. Make minimal changes to push each section behind an interface. Write tests against the interfaces. Then you have the freedom to rework each section independently of anything else that may be going on, and seperately from the live version of the application (because you are rewriting against the test suite, not in the context of the application).