These are the characters I'd say are 100% locks at the moment to be in the next Smash Bros.
Little Mac - He was already next in line for classic characters to be made playable after Pit and the fact he got his own revival with Punch-Out !! for the Wii pretty much seals the deal.
Ridley - He's the only truly iconic character from a long running series who's been in nearly every game in that series to not be playable in Smash Bros. Plus he's easily the most requested Nintendo character since Brawl was released so it's pretty much guaranteed a spot this time as well.
Palutena - She's the only character other then Pit to be in all three Kid Icarus game and in Japan the series is called Palutena's Mirror. She's also the second most important character in the games since she's basically the Peach and Zelda of her series. Plus Sakurai himself was behind the last game from her series and in sales it actually did pretty good. So yeah, she's in.
Chrom - Roy was the recent Lord when Melee was being developed and Ike was the most recent when Brawl was being developed. Since the new Smash Bros start around last Spring, which is the exact time Fire Emblem Awakening was released in Japan, that makes Chrom the most recent Lord guaranteeing his spot.
Whoever the major humanoid Pokemon is for X and Y - Since Black and White was released in Japan during September 2010, and that team went to work on X and Y right after, it would have been in development for at least 1.5 years before Sakurai finalized the roster which he probably did around last Summer. When he went to Game Freak they probably told him who the Mewtwo/Lucario type of Pokemon for X and Y will be and that's who will be making an appearance in the next Smash Bros.
Pac-Man - Since Namco is working on the game and Pac-Man is their most iconic character, I would be shocked if he isn't playable.
Characters I think have a really good chance but wouldn't quite call them locks yet.
Bowser Jr - He's become a permanent part of the Mario series by now having appeared in every platformer since Sunshine. Since he's the most important villain behind only Bowser to the series now, he'd be the most likely Mario character to get added. The only thing that would hurt him is if Sakurai decides the main Mario section of Mario, Luigi, Peach and Bowser doesn't deserve another character which I don't really see happening. Of course Mario had 5 characters in Melee and Sakurai gave it only 4 character in Brawl so who knows. Of course most of that had to do with the fact there were still a lot of other iconic non Mario characters that needed to be added in Brawl so Mario wasn't given more. But now that there's less iconic characters to add this time, Mario will probably be given at least a 5th spot making Bowser Jr more likely.
Paper Mario - He's been in 4 games now that have all been million sellers and is basically it's own unique franchise at this point. I wouldn't be surprised if he's considered his own series and put next to the RPG characters instead of the other Mario characters to show just how unique he really is. The only thing that would hurt him is if Sakurai doesn't consider Paper Mario different from the normal Mario series and if Bowser Jr is given the 5th Mario spot, he might not want to give Mario a 6th character on the select screen, leaving no room for Paper Mario. I hope Sakurai would consider Paper Mario his own series since he really is and would count as a new franchise added to the series like Yoshi, Donkey Kong and Wario are. But I've seen some people who consider Paper Mario part of the normal Mario series and so Sakurai might as well. I hope he doesn't but since I don't personally know the man I wouldn't bet anything right now.
Dixie Kong - She was originally planned for Brawl but got cut early on in development. I'd say Sakurai views her as the third most important Donkey Kong character and since Donkey Kong had a resurgence in popularity recently thanks to DCKR, I say her chances are very good. Only thing that might hurt her is if Sakurai wants to put in more villains and makes King K Rool the new Donkey Kong character instead. I think because of her original planning for Brawl, Sakurai finds her more important but I wouldn't bet on it quite yet.
Toon Zelda/Tetra - There was a Toon Zelda and Toon Sheik that were also originally planned for Brawl but got cut early as well. Since Phantom Hourglass ended up becoming the best selling handheld Zelda of all time last gen, and Wind Waker is getting the upcoming Wii U remake, that makes Toon Zelda still very relevant to the series and since Tetra is her alter ego, that would probably give this transformation pair a good chance. It'll depend on if Zelda is given a 5th character spot on the select screen which I'm guessing they would since Mario and Pokemon will probably get a 5th spot as well this time.
Slime - Dragon Quest is basically a Nintendo franchise at this point with all the games exclusive to Nintendo systems and Nintendo publishing them in the West. Since it has such a close relationship with Nintendo and is major huge in Japan, I think the mascot of the series being in the next Smash Bros is very likely. Plus Dragon Quest IX thanks to Nintendo publishing managed to sell over a million in the West, so it's not exactly an unknown franchise to Western gamers. The only thing I could see hurting Slime's chances are Square Enix not bothering to ask to have him put in for some reason.