His enthusiastic nature to beat the living hell out of anyone with those limbless fists is enough to put him in this list of mine.
Besides the fact that he could punch a jaw out from over 20 feet away, he also has some other useful abilities, namely his hair. With the use of his hair, he could glide and turn into a mini-helicopter! Well there's two special move right there. He also have different power-ups that could be use in Brawl as special moves for example “metal fist” and “lock Jaw”.

His smash attack would be a tough one to figure out. Maybe something goofy with his ability to changed appearance and outfits (like in Raving Rabbits). Whatever the case this character would be an awesome addition to the Brawl line-up.
Ōkami Amaterasu

This is another unexpected character that could be added to Brawl. First, some background story. Okami Amaterasu is actually a Goddess who has reincarnated into a White Wolf to defeat some evil demon named Orochi.
This Goddess, as her character stands, already earned enough point to be one hell of a female fighter. But how does Okami fight? This is the only character that can match Viewtiful Joe's style. She has the ability to paint in drawings using the celestial brush to attack or other defensive and useful ability however I can only see this working in the Smash attack. More on that in a bit.
Hey Wii, this is the perfect time to incorporate that damn Wii-mote effectively for once.
Realistically though Okami's special and regular moves would probably reflect those weapon that she uses that include the mirror, the rosaries, and the sword. It depends on how Brawl once to split it to make it balanced.
Maybe the mirror could be used to deflect projectile or absorb them and restore health like Lucas and Ness? Who knows, this character can have hundred different combinations.

Her smash attack would have to be the Celestial brush. Maybe is a combination of Veil of Mist technique (slows down time) or the Thunderbolt technique. Who knows, maybe all the advance technique one after another on the screen. Whatever the case it would be really cool to look at while your character getting his/her but kicked.
Banjo-Kazooie

Now this character is definitely gonna get some love from old 64's fans. This classic characters has a simple history; namely there is this bear (Banjo) and this bird (Kazooie) who goes around in different adventures to save the world and save people like most heroes do.
What makes them awesome is that for the majority of the time, this duo almost never leave each other via Banjo wears a backpack with Kazooie in it. Together they perform a number of different moves from running, pecking stomping, and even shooting eggs. This duo special moves is very easy to make namely what I mentioned above already.
Smash attack? Easy, how about the Jinjos thing that allowed Banjo-Kazooie to kill Gruntilda at the end of the game? Yes I know it looks goofy but for christ sakes we got a brown bear wearing a backpack which holds a breegull.
Since this game was made by Rare (who made the original Donkey Kong Country games), it hard to imagine why this character couldn't be included.
So that's it. My list of all the character that could had been in Brawl. It a shame but what can you do except send hundreds of letter of begging?