Hmm, I thought it would be easy with the new Blender 2.5 but if it isn’t, no pressure; I’ll simply rework my storyboard. But yeah, I would indeed require particle simulation with Luma/Croma Keying especially for fire. I can give you the draft animation for you to work with the particles so you’d know how to go with it. 
Oh yeah, I WOULD require 3D environments! The only problem is that I’d require them to look watercolored (I suppose there are some renderers, perhaps freestyle, capable of doing that) so low-poly with painted textures and correct lighting should be okay. But despite animating it once the renders of each object should be separate for vector interaction. Transparent PNG sequence are awesome!
If you can do that, you’re my Jesus! 
If interested I can hand you the concept arts of the areas and storyboards (for help with the cameras).