Here's been my theory for a while (I only missed Snake, the Pokémon Trainer, and ROB on the Brawl roster). Granted, I guessed about 7 or 8 extra characters.

Keep the 39 Brawl characters. Give Luigi a few more Luigi Mansion(s) moves. Make Toon Link more based off the recent handheld games, and Link more based off Skyward Sword. Give Falco a few more new A-attacks, and make Wolf more flashy and unique.
Re-add Mewtwo, and make Roy de-cloned and have a finesse-based move set of mostly stabbing attacks with some slashing moves (like how he fights in Sword of the Seals).
Add Paper Mario, Bowser Jr (more Galaxy and NEW SMB, less Sunshine), Dixie Kong, K. Rool, and RIDLEY (all caps because he is the biggest Nintendo-owned elephant in the room).
Maybe add the main character of a new Fire Emblem game.
Add Kamek because Kamek is awesome and because everybody who ever played Super Mario World 2 and Super Mario RPG loves Kamek. Can I get AMENNNN from MAH CONGREGATION=???
Maybe add Samurai Goroh because I like him. Yes, Goroh for the win!!!
Add a Generation 5 (and a Generation 6 Pokémon if it comes out by then; Gen 4 started in 2006; Gen 5 in 2010; Gen 6 will probably start in 2014, about the time SSB4 will be nearly finished), and maybe add another random Pokémon.
Add a couple of retro/random/less well-known "WTF?" Nintendo-owned characters. Starfy, Saki, Takamaru, the Balloon Fighter, Wart (Super Mario Bros. 2), Issac (Golden Sun), Bubbles (Clu-Clu Land), Mach Rider, Sukapon, and Lip would all be included in this.
Add 2 third-party characters, and maybe 3. Tails should be considered (Knuckles hopefully as well, given that he is awesome!), Pac-Man definitely should be considered (he is a true icon of gaming), and maybe Geno because Super Mario RPG is epic, and so was he.
But the one third party character smash needs, the biggest elephant in the room, is none other than the one and only...
....MEEEEGGGGGGGGGGGGGAAAAAAAAAAAAAAAAAAA MAAAAAAAAAAAAAAAAAAAAAAAANNNNNNN!!!!!!!! (YES!)