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.