My #1 pick, Quote, has a mechanic gift-wrapped: his experience bar.
In Cave Story, killed enemies drop energy crystals that fill the experience bar for your currently-equipped weapon. When you get enough energy, the weapon levels up, becoming more powerful and often changing in some other area (such as range also increasing, the Bubbline behaving much different across its levels, the Missile Launcher firing three missiles at Lv. 3, and the Nemesis actually getting weaker as it levels up).
The highest level you can go to is 3, though you can usually fill the bar again after hitting 3 to make a buffer...since getting hit makes you lose experience, and potentially even level down.
This would be fairly simple to translate into Smash: whenever Quote hits an opponent, his experience bar (one for all his weapons, not multiple individual bars) fills, and he can level up to increase his weapons' effectiveness; maybe he could even get an additional boost from landing KOs. Getting hit or KO'd lowers his experience. (I've seen someone suggest that you could bring in the energy crystals and make Quote play Coin Smash all the time, but I think that may not fit a regular match that well.)
I don't think Quote needs this mechanic, but it would be fun to play with, especially depending on which weapons are used in his moveset.