Honestly i think the game needs Crash, Spyro, Snake, and Cloud to be perfect. Id take an Assassins Creed character as well because i love them games but those 4 will make this game perfect.
Crash, Snake, Spyro, Pyrimid Head, a Resistance rep, Wander, Norman Jayden (Heavy Rain), An AC rep
Patches the Hyena (Dark/Demon's Souls) for All-Stars! His level three could have the player leave the match, enter a random match, and get one-hit-one-kill's on everybody! xD
prince of Persia moveset: http://community.us.playstation.com/t5/PlayStation-All-Stars-Battle/Prince-of-Persia-in-all-stars/m-p/38273897#M125640
I'd like a Chimera from Resistance. It'd be just like Radec, they chose him because the Helghast are the face of Killzone rather than the good guys Jan Templar, Rico, etc. The Chimera are more memorable characters than Nathan Hale imo.