I've been in similar code-needs-rewriting situations. I've mostly gone for the step-by-step approach, rather than stop using oldcode one day, and start using newcode instead.
Remember that you can apply strict and other pragmas to a block, you don't have to make the whole thing compliant in one step.
Adding -w or use warnings will often turn up things that the code works despite, rather than because they are there, so be prepared to do some head-scrtching and work out the proper way that function should be working.
Testing - mentioned by several people already, but here just to re-iterate it, test as you go along so you know which change broke everything.
Use wrapper routines when a current subroutine works, but could be called better, so that parameters are localised, pre-processed or passed differently to the new one. This way, new code can use the good function, and old code can use the old one until it's converted. If the old sub is in a library, consider logging each time it's called, so you can figure out which scripts still need converting.

Hopefully after making these ad hoc fixes, one day you'll look at the code and realise that it's just a few hours work to make the last few changes, and in the meantime, the new code you write can take advantage of the new functions and pragma.

the hatter