To avoid the trip to AE you can do it in Premiere, but it does increase the complexity of your timeline. You use the Track Matte Key effect, plus a colour key effect. It's a little tricky, but here's the basic set-up:
start with your three layers. On the bottom, the background that the dancing man is going to be in front of. Could be empty if ...
In your timeline, stack the matte clip on top of the character clip and add the Ultra Key effect to the matte with the red color as the key.
Nest those two clips, and place another Ultra Key effect on the nest, this time keying the black.
You'll probably have to mess with the ultra key settings a bit (transparency, choke, and soften) for both ...