How much is weapon damage actually contributing to the player's attack? Would it matter if they are rolling 1d3 (gauntlet, one handed) vs 2d4(scythe, two handed)? I know you mentioned Vital Strike, but they wouldn't get that on Vicious Stomp anyway.

Lets say your player is using Power Attack(PF, with +8 BAB) and having a decent strength(22), you are looking at what, 1d3 + 12(ave 14) vs a vital strike at 4d4 +18 (ave 28). A 'half damage' attack for the cost of a single feat(Vicious Stomp, well 2) isn't too bad. What other feat is going to give that much of a return? That said, to take the feat the player needs to have Improved Unarmed Strike, and the easiest way to get that is through a Deep Red Sphere Ioun Stone socketed into a Wayfinder. 8k, but it doesn't cost a feat or a level. There is probably something similar in 3.5 but I am not aware.

If you are just looking to up the damage, get someone to cast Greater Mighty Wallop(3.5) on them or an Impact Amulet of Mighty Fists. Or just Merciful and Sapping gets you up to 3d6 for the cost of a +2 Amulet. Granted its nonlethal damage, but knocked out is just about as good as dead most time.