Hopefully there is something in your frame that is fixed that you can track for scale and rotation. The procedure would be to stop all the camera movement by stabilizing the footage then perform your key then scale as necessary to fix the framing problem. And by stabilize, I do not mean warp stabilize. That will do you know good and cannot work on the green screen anyway. I mean you lock in scale and rotation so that something, like the actors torso, does not moved in the frame at all. Only then do you have a chance of removing the offensive motion. If you could post the shot then I could give you some ideas. I have had to do this several times because of inexperienced camera operators. I always felt like sending them a bill.
If you don't mind keeping the movement of the shot, you can just use motion tracking (After Effects Help | Tracking and stabilizing motion) to make your new background match the camera movement. However, if you don't have tracking markers (or even folds or creases) on the green screen, this will be difficult.