After Effects will also help with some of the specific stuff you want to do, like traveling mattes for the stage actors crossing over into the screen. There's video tutorials over at creativecow.net and videocopilot.net that are pretty good. Also there are forums dedicated to this kind of work. They might not be as "fanedit" friendly as we are here, perhaps, but I think they will help with specific advice.

Creativecow is kind of a nuisance to navigate, but here's some tutorials for After Effects.
Creative Cow AE tutorials

Videocopilot.net

Although, in my opinion, it would be a crime to make Rocky Horror completely in Black and White. I thought the original idea was to make it black and white until Frank shows up. His lips aren't that saturated to really make the gimmick work very well.

Here's one that has some rotoscoping in it.
linky