Overlay two videos and match/track background
It sounds indeed like a non-trivial solution, that will require you to get proficient with motion tracking and/or compositing.
For a 3D way to do it you would need to track the footage and solve the camera.
The success of the operation would depend entirely on the kind of motion from the cameras, if there is parallax on the scene then you might be able to recreate 3D info. If you track features for which you know the scale in the real world, then use it to set the scale in the 3D reconstruction.
You could then to re-project the image into some geometry, so that you have a reconstruction of the 3d space as fixed points, and a image projected from each of the positions on the camera at a given frame, the UVproject modifier will allow you to use the camera as a projector or you can use a lamp that is parented to the camera to project the image as texture.
You would need to do the same for the other image and manually reposition the camera so that the projected images coincide with those of the other camera.
A non-3D would be to create two un-distorted and stabilized images out of the video. Those new pieces of video can be overlaid using difference mode in a mixRGB node for clarity. One of the videos would need then to be rotated, scaled and possibly distorted so that some the features of the track correspond to those in the other image. Note that the difference in perspective from both images might prevent you from getting a perfect match. You won't be able to invent what the camera did not see.