Some ideas...

[Pirate Guy]

First I love these ideas. For the fists idea I have thought about this alot and here's what I have come up with:
Level 1 fist unlocks Right Jab
Level 3 fist unlocks strike ( A skill that is a striking motion )
Level 5 fist unlocks Left Jab
Level 8 Down-strike ( A motion where you bring down both fists on the enemy )
Level 12 fist unlocks Upper Cut
Level 13 fist unlocks Spin Stirke ( A motion where you spin in a circle with fists out [Like a sweep] )
Level 15 fist unlocks Fist O' Fury
Level 17 fist unlocks Smashing Stike ( A motion that smash's the enemy for alot of damage

These are just ideas tell me what you think!