One of his developers stated they were trying to reach Superbot and Sony to ask for his inclusion in All-Stars but they didn't get back. With the recent push for Abe I think Superbot will try to get him for DLC
ABE and CHIMERA FOR PSASBR
Crash seems likely as DLC, since it means Activision can get extra revenue from the game (greedy mfs). This also applies to Spyro, so it seems likely that we'll see a joint Crash and Spyro dlc, together with a mash-up stage. That should be how the dlc is organized, two rival characters plus a stage.
Others that seem likely are Kat, Abe (because Oddworld Inhabitants basically gave the thumbs up to that), Snake and Cloud. Monkeypaw games, who acquired the rights to Tomba, also expressed interest in having him in the game, so there's another possibility.
I suppose Lara Croft is a possibility too, the game could use more women. Also an Assassin or Rayman (The former, like Big Daddy, shouldn't really be in the game if you ask me, but it still seems likely.)
Also I don't see why Kazuma Kiryu couldn't have a place.
I'm thinking an Assassin could be Snake's rival, or Abe for that matter since he's pretty sneaky
Any two from Abe, Rayman or Tomba could be rivals to one another, since they all feature in side scrolling games.
Not sure who I'd pair Cloud up with, maybe Kazuma since they're both sort of strong, silent types.
Kat could work with Rayman.
Lara Croft.... maybe Snake?
Kat - Vita representative.
Snake - One of the most iconic and popular characters of all time.
Ezio - Assassin's Creed is getting really popular. Especially with the casual crowd.
Crash - Nostalgia.
Abe - The developers said they wanted Abe in. Unique moveset potential.
Tomba - His game was a gem on the PSX.
Dart - Cult classic JRPG. This would turn some heads.
Spyro - Nostalgia.
Kat-Vita representation, Female, highly requested, Omar loves her.
Crash-Nostalgia, hopefully Activision budges.
Spyro- same as above.
Abe-Developers want him in, be an easy addition
Tomba-Same thing as above.
Nathan Hale-Would be a good counter to Radec, developers have a good relationship.
Dart- The Legend of Dragoon license was just renewed a couple of months back, so there may be plans on Sony's side to bring his as DLC and then reboot the series for this or next generation.
Kazuma Kiryu-Great third party brawler character, would be like the Frank West of All Stars with some of the crazy stuff he used to beat people up.
Team Ico rep- Ico & Yorda would have unique gameplay, Wander would be fun especially a SotC stage.
Cloud- a final fantasy rep is a must in this game. Cloud can definitely make a lot of fans happy.
Ethan Mars- Quanitc Dream is playstation exclusive. Give them some more mainstream success. Heavy Rain was a great game but I know people who only have PS3 that have never heard of it. Would give them publicity for Heavy Rain and Beyond. Ethan would be another Frank West type character.