How about when you defeat a gym leader, in addition to the badge, you get a TM?
So if you beat the water gym, you get a badge and the TM scald or some other water type move.
Or instead of a TM you could get an item like a Macho Brace or Lucky Egg.
Or how about Emeralds?
It's just an idea, if you like it, yay, if not, oh well...