If the camera and background are both stationary (or perhaps very near stationary) you should be able to extrapolate a background plate from looking for frames where the man and paper are not blocking that part of the shot. Once you have that background plate, you can mask the newspaper and expose the appropriate portion of the background plate.
This works best if the camera isn't moving, though you may be able to do a camera tracking in the event of small camera movements and still get workable results by matching the position and angle of the background plate to the camera (though it will likely require far more advanced background plates to account for any perspective changes). With anything more than minimal movement of the camera though, the perspective changes will become too severe to compensate for and you won't be able to build a background plate from previous/future frames.
At that point, you would actually have to build a model of the scene in order to be able to render out the background to fill in with perspective adjustments and that would be far more complicated than re-shooting.
Note that this also does still require frame to frame adjustment of the mask and requires building the back plate by hand as well. It is still non-trivial, but isn't quite masking frame by frame in Photoshop since the rotoscope tool should work for it.
If shadows are visible on the background as well, then you may need to make some animated masks to emulate the shadows on the background plate as well. Either way, we're talking about a pretty elaborate operation most likely depending on the quality you need. If any shadows from the actor are visible though (particularly soft shadows against not flat objects) the quality level will drop like a rock and the complexity will go higher fast.
If you do get hit with shadow issues or background movement issues (and reshooting really isn't an option) you may actually be served best by replacing the background entirely). If you build a fixed background plate that doesn't have any shadows from the actors, people are not super likely to notice the lack of shadow compared to a gap in the shadow or a reconstructed shadow. It would involve even further rotoscoping, but might be easier than trying to build a believable shadow.
Reshooting really is the best option, even in the ideal case though.