Check out some of Andrew Kramer’s tutorials on VideoCopilot.net. Though his tutorials are for After Effects, the concepts will still apply.
From your description, it sounds like you’re dealing with the absolute worst-case scenario: a moving subject, a moving camera and moving background objects. You’ll most likely have to rotoscope your subject by hand, a task that will be VERY daunting due to interframe motion blur. And even if you can cut a clean mask, you’ll have to figure out what you’ll put in the “hole” he leaves when you mask him out.
Just so you know (in case you’re asked to do this again in the future), this scene should have been shot in two different takes. The first would have been a shot of everything BUT your disappearing man.
The second shot would have been of ONLY your disappearing man, shot against green-screen, with the camera moves matched exactly to the previous shot.