Simply dowload the AE trial and see if it works for you. Everything else is pointless - your question is like asking a painter for which brush, color or technique is "the right one" when there's a million ways to paint something and they can all look great...
Mylenium is right - this is what After Effects is designed for. There are a lot of different ways of working.
In your case, I would recommend doing some keying on the clip, then duplicating the layer with the clip on it multiple times. You can use position, scale, and most importantly time offset to make it seem like each "person" is unique, even if it all comes from one clip. Once you have all the clips in position, then you can make your background.
I suggest you try both Premiere Pro and After Effects. As someone who makes music videos as well..
I find Premiere is great for cutting the piece together. Then After Effects is great for adding motion graphics and special effects. But both are professional applications so be prepared for a learning curve. Good luck!