Bunraku style puppets against a green screen (or blue). Puppeteers wear green suits (much like The Book of Pooh). That would work.
Just make sure that the puppets you have do not have too much thin fur coming off their bodies (nothing long). The reason being that the fur will be a nightmare to key out in post production. If there are any editors out there they will poably say the same thing. If you can design the puppets to have more of a clean line/short fur around them, it will look much better after the background has been keyed in.
Here is a great example of a cat puppet that would work great against a green screen (minus the furry cheeks and top of the head). Just something to think about.