http://uk.youtube.com/watch?v=j0xAwX34G_Y How is it you can "paste" a face over a video? It can't be frame by frame edits? Surly...
One way that I would do it is in Adobe After Effects. Open the clip you want to edit and then import the face image. Then just keyframe the face position. I'm sure there are other ways too.
Another way to do it is to use Sony Vegas and paste the face onto a new layer. You would have to move it around to match the body though. Probably not every frame, but it would definitely take some time and patience...