Well, I never really play Rohan, but I would usually get Gimli around the mid-game (along with Aragorn), as a major support hero. And adding a power with him would spice him up a bit (I don't really see any balance work).
Yep. Give him new power, give him a high-rank skin, tweak his other abilities so his new one doesn't overpower himself, then he will be awesome. Just to throw out some more ideas...
Axe Throw - level 1
Leap - level 3
Jewel's Lust - level 5 - Gimli bends to the ground and out of a dust cloud (for effect) he pulls two money chests that supply 300-400 resources. Recharge time would be sorta long because Rohan already has Eomer who has pillage, so this should be balanced out to fit alongside Eomer.
Slayer - level 7 - make it have a longer recharge time if he gets Durin's Axe below.
Durin's Axe - level 10 - instead of this being a passive ability as slayer already makes him powerful, Gimli will get this ability. What it does: he swings his axe up (this will be a version of Gandalf's wizard blast, maybe slightly smaller) and then he swings down (causing another wizard blast but goes all around him like WoP and with a small earthquake effect or something). The anims from slayer could be used for Gimli swinging his axe but with something added to make it original.