You did not say which application you are using so I am going to assume that it is Movie Edit Po. For the clip that was shot with a green screen background, place the clip in the time line, select the clip, then go to "Effects" then "Video Effects" then "Chroma Key". Choose the color green and the background should dissapear. You may need to adjust threshold and fading range to get the look that you want. Next, choose the new background that you want and drop it on the track below the green screen track. That should take care of it. You may need to adjust the video levels on each track to achieve the balance you want, but this should get you pretty close to what you want to do. If I have missed something, add comments to your original post and I will dig deeper if needed.
If you follow John's advice, you should be able to minimize the "shimmering". Otherwise you are absolutely correct, if the green screen is not either properly stretched or the lighting is off, it is hard to get rid of the shimmering completely. Sometimes you can further reduce it by adjusting the video levels of each track or even adjusting the color a bit. Unless you decide to re-shoot the green screen, it will be difficult to get rid of it completely.