Have you considered reworking unarmed combat? Currently if you have arms you punch, if you don't have arms you kick, if you have neither arms nor legs you bite. (Barring vampire.) If a person wearing Boots of Kicking preferentially kicked in melee, or if the actual attack performed depended on relative skill levels, it might make the boots of kicking more useful.
Another model might be to take a page from Crawl: if the limb is free, you have a (skill)/(skill+X) chance of attacking with the limb whenever you make a normal melee attack. X can be tuned for balance. Allows a skilled boxer who picks up a knife to keep punching between stabs, or someone who is good at kicking to get free kicks once in a while. X could include a constant, modifiers from e.g. encumbrance, and even be reduced by stats. How many free attacks per round of melee are possible would be a different discussion: should a highly skilled boxer, kicker, and biter be able to stab with a sword, punch, kick, and bite all in one round? Etc.