First of all, I'm not sure you will find a CPLD capable of 5V outputs. There are devices (Lattice ispMACH for one) that are 5V tolerant, but that simply means you can apply a 5V INPUT without harming the device. If you can tolerate the low-speed that would occur if you use open-drain outputs, then you might be able to use one of these devices.
Since you've got 50 ins and 50 outs (if I read that right), you are probably talking about a 144-pin QFP package. These are 'hand solderable, but you'll probably need a magnifying light at the very least (unless you've got really good eyes). And a good iron.
But otherwise a CPLD will certainly be able to do what you want. I assume you'll want some kind of input (switch or command from the uP) to tell the CPLD to switch its pin-mapping, right?