Yeah, greenscreen is the best way to use displacement easily, to prevent the need for frame-by-frame masking. For stairs, its just a matter of laying a greenscreen out over the stairs for them to walk over, keep the camera locked off, and shoot the background plate of the stairs, then composite the two together. Likely, this will require several greenscreens though, which could make it trickier if you only have one. So yeah, basically, you have to have a greenscreen behind them at all times.
If it isn't possible, then you can use masks to remove the background from certain shots, but that will be frame-by-frame hand tracking which takes a long time.
Not sure if you've seen it yet, but here is a tutorial
for that particular effect, worked up by Tarn.