This is my idea:

What if you start with Raiden as your main character, using him to fight other people along the way. Then slowly, as he explains his motivations to other characters, you can take them on your "team" and build up an MK squad to fight the bad guys.

When you're challenged by somebody in story mode, you can pick from whoever you got so far, either for a one on one fight or a tag team match. If you win you move on, if you lose, it's game over.