Start with getting your source control and deployment in order. If you have to, lock down production so that the only way to deploy is via a checkin. Then fix the rest of the ops and get all the configs into source control, especially the NGInX config. Make sure memcache is set up for scaling later.
Then start in on the code. Start by writing some basic tests (you'll probably have to do this as a series of curl commands because it's unlikely the interfaces are clean enough to do it any other way). You'll need the tests to make sure everything else you do doesn't break major functionality.
Then do the easy stuff first. Fix the parts that curl itself and make it a real API call. Fix the dependency management. Compress the NGInX file by eliminating whatever rewrites you can by adding routing into the code. Test often, deploy often.
Enable tracing to figure out what code can be safely deleted. See if you can find old versions sitting around and do diffs.
Replace all the code that accesses the data store with a data access layer. Once you've done that, you can bring up a new data store with a proper schema. Make the data access layer write to the new data store and do queries by joining the old and new as necessary. If possible have the data access layer write any data it reads from the old data store into the new one after it serves the request, and read first from the new data store. Log how often you have to read from the old data store. In theory this will go down over time. Once there isn't a lot of reads from the old data store, write a program that runs in the background migrating the remaining data.
Most likely you can do all of that without anyone really noticing, other than teaching them a new way to write code by doing a checkin instead of in production. Also you'll have to teach them to use the data access layer instead of directly going to the data store.
After you've done all that, don't try and rewrite the code. Spin up a new service that does some small part of the code, and build it properly with frameworks and libraries and dependency management and whatever else makes sense. Change the main code to call your service, then delete the code in the main service and replace with a comment of where to find the new code. Maybe if no one else is working on that service they won't notice. Make sure new functionality goes in the new service with all the dependency management and such.
Keep doing that with small parts of the code by either adding into the new service or spinning up new micro services, whichever way you think is best. Ideally do this in the order of how often each function is called (you still have tracing on right?). Eventually most of the important stuff will be moved, and then you can decide if you want to bother moving the rest.
Hopefully by then you'll have a much better velocity on the most important stuff.