If I understand you correctly you only have the video and the spaceship in the scene. You will have to create a mask for the background behind the mountains, remove the background from the first layer of video, and then insert the background as a separate media plate. Unless there is no camera movement, this will be a lot of work if you want it done properly, since you will have to recreate the camera movement. Let me know if you have more questions.
Placing two meshes at each side and using them to occlude the spaceship could work, yes. Just make the spaceship material transparent once it is behind the transparent meshes. Let me know how if this works out.