I was around for the Google Webserver rewrite and it was actually a rewrite done by refactoring not clean slate. It's amazing what you can do with disciplined refactoring, even moving to a new language.
If you have original code, you can always write a test suite based on it, unless management is averse to this. (Begging the question why they're not averse to a rewrite.) Like any test suite it is not going to be complete.
Ultimately it's best not to get piled on by rewriting really and often in small parts. (Carmack way.)
First, you start with a slow but correct prototype in python. This can then be refactored into python closer to C, thinking about the data structures and functions that will be needed in C.
Then, you can refactor these bits into C. I've usually done this one module at a time.
You then write python bindings to this new C code. There are a number of shortcuts available here with differing tradeoffs, but you can just use the Python/C API.
In the end you're left with a C library, some bindings, and some python that just calls to the python bindings for the C library.
It would not be a huge leap to go from that to a full C implementation.
Nothing I've said here is C specific, so you can do the same with C++.
There are upsides and downsides to this whole approach. For me, one of the downsides is the amount of stuff to remember, especially some of the quirks of extending Python.
I find it easier to start with something correct but high-level in Python and work down to something easier to translate into C, even if I skip straight to the writing in C bit. I have found this usually leads to a significantly better design whilst it was still Python. You can also test the behaviour of the C and python modules against each other.