I love the way "The Lost Vikings" did it, but that was one player, multiple characters (CV3 style).
Very good place to start, Lost Vikings with a Multi-player option. Each Character could have 4 possible States; Player Control, AI Control, "Stay", and Out of Play. Four Different Classes available, refered to by surname (Example: Belmont, DyNasty, Lecrade, Belnades) each of which as a unique Primary weapon and a set of unique Sub weapons. If normal multiplayer is enabled, a 2nd Player can control any of the available characters not in use. An advanced multiplayer mode could be an unlockable extra, allowing for up to 4 players to play as any character. (even if that character is being used by someone else.)
Normal mode, is the "Plot mode" the four classes reflect the character's personality and are locked to each character's respective gender. After you beat the game, you unlock the customization options, Including gender (Want to be a female Belmont or a male Belnades? no problem.) and clothing color (Like Joseph's Cloak from SotN.)
Fourswords, was played with each player using their own GBA, The same could work for a Metriodvainia game on DS, (Wireless conection would make it far more convenient too.)