MeleeMan
Smash Ace
Not true. Mario could be Dr Mario, Strikers costumeI haven't played that, but lots of games have that, which I think would be somewhat cool, but the problem is, not many characters would have much customizeable options. Maybe Snake (face paint), Fox (every friken Star Fox game changes his looks), Kirby (hats), Pikachu and Jigglypuff (hats and junk), and...I think that would be about it (depending on who makes it into Brawl).
Peach - Daisy, Old dress, Pony tail summer look
Samus - Dark Samus, different suits
Zelda, Link, Ganon- Hell, they could switch between OOT, WW, and TP versions for different costumes
and thats all I care to think about right now. but they could def. do it. These characters have been involved in enough games to have a bunch of different options.... except G&W maybe