Software for pixel videos montage

Hello, tigsource!

For a long time I'm thinking about trying new ground in making pixel-based videos. Think 8-bit demakes, 8-bit cinema, Dan the Man or even Paul Robertson's animated shorts. I've animated scenes in Photoshop before (for example), but I risk losing my sanity when dealing with dozens of frames. So I'm looking for software that will allow me to:

1. Take my animated character gifs and move them around;
2. Add backgrounds, make parallax layers and all the good stuff;
3. Maintain maximum pixel crispness;
4. Obviously add music and sounds.

That's like doing mockups on a whole new level! Or fake game trailers maybe.

I hope some of you guys have had experience with this kind of software and would point me out in right direction.