As Jason says, if the camera is stationary throughout, this is probably doable.
First, work out how much more scene you need to create, by opening the video in After Effects, and dragging it to one side until it looks right. Export a frame from that comp as a still (something lossless like TIFF is best).
Open the still in Photoshop, and build your "clean plate" - try using the Content Aware fill tool. It works suprisingly well sometimes. Any dodgy bits, go over again with the Content Aware brush, then use a soft Clone Stamp to fill in any further bits that look wrong. Save your new still image as a TIFF.
Open the new TIFF file in AE, and put it behind your main video in the comp.
Draw a mask around your main video, and feather the mask until the edges start to go transparent. Drag the edges of the mask, so that you have a nice gradual feathering gradient into your clean plate, but make sure the other edges of your video aren't becoming transparent (make the mask much bigger than the video on all sides except the side you're trying to fix).
Finally, add some noise or film grain to the still image layer - it will help "sell" the shot more, and make the still look more like video - don't overdo it - a little goes a long way.