Going into a situation like that, you basically have two options:

1. Try to convince your boss to give you a large chunk of time to work on writing tests instead of fixing bugs or adding features. (Good luck if you try this...)
2. The next time you go into the code to change something, first create a test script which exercises the code you're going to be changing and, as far as possible, defines how it currently behaves. Then make your changes, update the tests to match your changes, and run them again to verify that everything else still works the way it used to. (Or, if you prefer to drink the TDD kool-aid, change the tests first, run them to see them fail, and then change the code so that the tests succeed.) If you do this each time you make a change, you'll have an ever-growing test suite which will eventually cover most, if not all, of the code.

As far as tools, I've been perfectly happy sticking with just Test::More and occasionally bringing in Test::Warn or Test::Exception where needed.