prince of persia
why because he would have a very athletic and agile playstyle, with some amazing supers, look in the miveset i created for him HERE: http://community.us.playstation.com/t5/PlayStation
he could be the ubisoft rep and and assassian could be his rival, ubisoft is a company thats always stood by each sony, nintendo and microsoft so they arent biased towards one company.
there have been psp games with exclusive content for the prince, and hes one of ubisofts most famous franchises, and he is a gaming icon, that helped create new game mechanics.
prince of Persia moveset: http://community.us.playstation.com/t5/PlayStation-All-Stars-Battle/Prince-of-Persia-in-all-stars/m-p/38273897#M125640
Ty the Tasmanian Tiger. He is owned by ubisoft and people have already pointed out that Ubisoft isn't against working with sony. Ty would be a ranged character almost certainly. A lot of people have played Ty the Tasmanian Tiger. I would think square would be attacking with his rangs, Triangle for bite attacks, and Circle could change which boomerangs he is using. I think it would be best if he was in his outfit from the first game and his alternate costume being either his out fit from the last game or his brother.
Legacy of kain were great titles on playstation consoles and blood omen was an exclusive before being ported. Both characters have great moveset potential and original powers that would make for original characters in all stars.