I did something like this once. I had to export all the frames to png's, then go into photoshop and edit each picture individualy. Took about 2 hours for a 5 second clip (was a big area, little detail).

I should mention, though, that i got the look I wanted and it was worth it.

Hmm, I'm not sure if I understood the problem completely... but principially you can make a mask for a moving object as well, as long as the background differs enough from the object. You can apply a "Chroma Key" filter and pick the background color (there are already presets for blue screens), and use its "Show mask only" checkbox. Probably you need to play a bit with thresholds and maybe add contrast&brightness. After rendering, such a clip could then be used as mask for your original clip.

You might be able to get away with using a mask or masks to get rid of most of the background, then try chromakey, then maybe a bit of manual touchup.

In some software you set up vector paths around your object, & it can get fairly involved, but then again so is manually retouching every frame.

Yeah...I guess what I was looking for was doing vector paths around objects like in Boris Red....which I can't afford! :-0

Other than that...I guess doing frame-x-frame paint out is the next best. Time consuming, but it probably is the best method for a shot after the fact.