I was thinking about this and it would be interesting if the skill in which you gain % when you gain a level would be a skill you have used during that level. (chosen randomly among all those you used, with also a few you didn't use in the equation)
I think it would be more interesting than it being completly random, and it could also help classes like invoker or assassins who needs certain skills at maximum to learn others.