How about:
2 clickers, one for regular simple melee, the other for simple melee with combos. The first remains as is, the second would allow you to hold down the clicker, essentially charging the combo. The less the bar is charged the weaker the combo. I'm thinking maybe we have a bunch of animations for the 3 types of hits, those being weak, medium and strong. When you're within hitting distance and you let go, rather than knock the character away at high speeds, you do your little combo thing hitting the opponent for x damage, where x varies between the 3 types of damage. While performing the combo, you'd be covering essentially the same distance as a regular simple melee hit and within the same amount of time. This gets rid of the feeling that you're just waiting around.
If both players do the charged melee thing, the one who charged it the most would do full damage, but would receive half or a smaller fraction of the damage. I don't know, make a counter animation and have the guy transition into his combo. If both are fully charged, or they both charged the same amount, they could do that thing numerous people have suggested, where they fight the way Majin Vegeta and Goku did in that one episode. I guess you could turn that into a mini-game, in the same vein as 1.2's HOWs (while the combo animations are going, both players are inputting the appropriate directional keys).
I don't know why a person would choose the secondary simple melee over the primary melee, though. The idea obviously hasn't really been thought out. Anyway, is it worth thinking about and expanding upon or should I try something different?