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
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.