Well, the only character I'm nearly 100% sure would end up in the next game is Bowser Jr. It just seems pretty logical. With New Super Mario Bros. Wii, he's kind of cemented himself as more of a core character in the Mario series, and after having Bowser for two games in a row, it wouldn't be too much of a stretch. It wouldn't be a Bowser clone, due to the fact that the characters are more like DK and Diddy Kong than Fox and Falco or Ness and Lucas. And he has plenty of material to design a set of moves from, with Super Mario Sunshine. Which is cool, because I can see myself playing as him a lot.
I would like to see Paula from Earthbound in there; she's probably just as obscure a character as Lucas in america, and as a girl she'd be a nice way to round out that group of characters. The only problem is that Ness and Lucas don't have most of those moves in their game. PK fire, Thunder, and Freeze all come from Paula/Kumatora. Lucas's Rope Snake was Duster's, and some other moves were also rearranged. They more or less stand for their entire game rather than their character. It would be nice if they put Ninten in, just as a funny way to laugh at us because we don't get the export on Mother. They would essentially be a Fox, Falco, and Wolf trio, but I would be so ok with that.
It's not likely to happen though.
Speaking of, Krystal would be a nice Wolf replacement, but only if she used her Star Fox Adventure staff as opposed to her Star Fox weapons. She'd be a bit like Zelda I imagine.
I'd KIND OF like to see them expand on the F-Zero series, because right now it feels like they're just holding on to him because they know they're not allowed to let him go.
Wolf Link b/w Midna would be nice. The timing is just a bit unfortunate, seeing as Twilight Princess was probably released too long ago to make it. I would also like to see Toon Zelda/Tetra playing as a double for Zelda/Sheik, which would be nice. Zelda would essentially be the same, maybe add the bow of light to her regular specials, but then tetra would be a cool way to not be a Sheik clone. And Tetra has been in more than one game, so I see it as more probably than Midna.
I've been waiting for a character that Wasn't in two consecutive games, and Roy is probably to only one who could fill that niche.
I'm all for Birdo, and (s)he's actually the only character who I would LIKE to see as a near-clone (of Yoshi). I'd like them to be sort of how Luigi and Mario are.
Speaking of Luigi, I will play as him much more if he get's more Luigi's Mansion-themed attacks.
Paper Mario would be really cool, but at this point they would have like five characters who are just "Character A but in a different form/art style." Still, he would be the best ever.
As far as outside-of-Nintendo characters, I wouldn't mind it as long as they do it right. They should feel a little less like part of the main band of fighters, and more like cool add-ins.