Video/Animated GIF advanced frame editor?

What sort of application could I use for example if I had a 5 minute video or an animated GIF with 50 frames, and I wanted to basically Photoshop replace an object, say a person's head, with another image for all those 50 frames? Is there some sort of smart tool that can do this or do I have to edit every single frame by hand?

I wouldn't mind there being a tool where I can paste the image in every frame automatically, and switch from frame to frame adjusting the position of it, I just need something efficient.

I've tried using Photoshop's import video into image sequence and tried editing with the animation toolbar at the bottom, but it's not quite what I want. I don't care if it's free software or not, I'm primarily using Linux but I have VirtualBox Windows XP if there's an excellent application that's not available otherwise.

Solution 1:

Use GIMP with GAP installed. It's free, open source, and runs on just about anything.

http://www.gimp.org/downloads

Solution 2:

Ulead GIF Animator can do this easily. You will need to reposition the head for each frame though.