There are two ways to approach this, both are using After Effects:
1. You build every clip within a mask, render them out (or precomp them), import them, and just move the movies around using conventional position keyframes
2. Stay with the fiddly bits, creating a mask template that is applied to every layer independently. Fiddly, indeed, but entirely possible once you get into the groove.
If you use precomps, and understand how they flow into from the pre- to the main comp, you can rough assembly all of the moves and then go back and position the movie clips that site under the mask. That is, you move your masks around and then tweak the movies' positions to make sure the hero is well-composed in each setup. AGain, not as hard as it seems. But I'd be doing this in AE.
Thanks bogiesan - I managed to get it pretty close using just Premiere, but will investigate AE. I knew there must be a simpler approach!