How would you go about removing a boom from a shot? Say the camera is fixed.

Get a clean shot of the background without boom, and superimpose that onto the shot.

Getting the clean shot of the background: Find a frame where the boom isn't in the shot. Or dump a frame into Photoshop and remove the boom.... i.e. via the clone tool.

2- What programs do you have access to?

I can't shoot it again; that's why I'm rotoscoping!

I have After Effects, but I could install cinepaint or wax. What other applications are commonly used? What do you use?

I can't shoot it again; that's why I'm rotoscoping!
You don't necessarily need to rotoscope this shot.

In case it wasn't clear, you don't need to shoot this again... unless the boom is dipping in front of the actor's hair (unlikely). You do need to find or generate a clean image of the background where the boom is/will be. You just need a clean image of the upper portion of the shot.

Then superimpose that clean portion onto your footage. You will need to cut/mask around the bottom part of the clean background so it doesn't go over the talent.

2- I'm not too familiar with After Effects, but it would be an excellent program for doing this.