Only photoshop and lots of patience.
I've recorded two macros / actions:
1. Duplicate layer, apply color changes to the second layer, duplicate first layer again and move it on top.
2. Convert image to Fallout color palette, save the image, close the image.
So I'll just load all frames of one animation set at the same time, go into the first image, run the first macro, and then use the eraser tool to remove the pixels I don't want (for the critters above it was the shirt / body). Once done, I run the second macro and done, next image pops up automatically.
It's fast, but you still have to work carefully or you will get sloppy frames like the ones above have at times.
In any case, the first critter took me about 8 hours and the second something around 5 hours of crunch.
Normally you would have to do a second pass on the animations, to fix shitty frames, etc.... I skipped that.