Wiseguy
Smash Champion
Good question. I judge a character's replacability on a number of factors.And you seem to be the only person that actually wants a huge overhaul of characters. most people actually expect 4 at most to be replaced, and people that expect more (which admittedly I'm one of), are really accepting that it's a possibility. You're the first person I've seen that wants a huge change in characters, though I'm interested in who you actually deem replaceable.
The original twelve charcaters should stay, in my opinion, as they have been with the Smash Bros. from the beginning. This includes Mario, Link, Fox, Samus, Pikachu, DK, Kirby, Captain Falcon, Luigi, Yoshi, and Jiggs.
Everyone else needs to earn their spot in the greatest game series of all time, based on the games they have appeared in in the years between Melee and Brawl. Peach, for example, has stared in her own games so she deserve to return, perhaps with updated moveset. Bowser and Falco have appeared repeatedly in supporting roles for various games so they too deserve to return. Someone like Young Link needs to be updated in the Wind Waker art syle and likewise Zelda and Ganondorf should be given a Twilight Princess makeover.
Characters like Dr. Mario, Ice Climbers and Mr. Game & Watch are fun and likeable to be sure, but they were lucky to be put in Melee and do not deserve to return in Brawl. Instead, other obscure-but-cool charcaters, like Pit, should take their place.
Finally, I think that supporting characters like Pichu, Mewtwo, Sheik, Roy and (wait for it...) Marth should be replaced by newer and more deserving characters. Mewtwo and Pichu should be replaced by Pokemon from the more recent Pokemon games (like Diamond and Pearl), Sheik should be replaced by Midna while Marth and Roy should be replaced by Ike and one other charcater from PoR or GoD. For me, the Black Knight is that character.
Edit: Sorry, SuichimoTheDragoon, that was a lame joke. I was referring to your actual name given at birth. I'm aware that SuichimoTheDragoon is only your alias.