I really like the upgrading idea. I also like Skill Slot idea. How about we put the two together? I propose this:
Instead of upgrading from gaining a badge, how about the Skills--essentially the same as HMs--upgrade upon gaining Skill Points? Each battle would give Exp and Skill Points. Upon gaining enough Skill Points, the Skill would upgrade. For example, Mijumaru's Surf would eventually upgrade to Surf II (Surf w/ Whirlpool) then Surf III (Surf w/ Whirlpool and Waterfall). The HMs would still be moves, TMs, that can be given for move slots, but the Skills would be given at birth. Some Pokemon would have more than one Skill that would be determined at birth, much like Abilities and IVs. For example, Pelipper can know Surf and Fly. At birth, like IVs, its Skill would be different.
Also, there would be a limitation on which part of a Skill can be used before a certain badge, much like HMs can only be used after getting a certain badge. So, to clarify:
--HMs would be removed and instead be split into TMs and Skills. A Surf TM would behave the same as Surf I, not Surf II or III.
--Depending on their type and movepool, a Pokemon could have up to six variable Skills (frikkin' Bibarel...)
--Skills can be upgraded through battles, which would give Exp and Skill Points. Skill Points per battle are set while Exp is not.
--Skills can only be upgraded so far until a certain badge is received. This eliminates grinding for Skill Points.
--A Pokemon's Skill gauge (where the points are allocated, much like the Exp gauge) differs for the Pokemon. For example, Wingull's Surf Skill gauge would be smaller than Mijumaru's Surf Skill gauge.
If there's any loopholes in this system, just let me know. I spent all of math class thinking about this. :D