I agree with Ke5trel. The only reason this is an issue is because the games drag on forever.
If the games lasted as long as they are supposed to, then people wouldn't hit level 25 every match. They would mostly end between levels 10 and 20, at which point the skills you have chosen still matter as you haven't gotten enough skill points for everything on the tree. As people said, it is possible to get every single skill in DotA, but it isn't an issue because games don't last long enough.
I am not sure about the speed at which you gain levels. I think this can only be determined once games are fundamentally balanced to last as long as they are supposed to. At that time, we will be better able to judge how fast Demigods should level.
There is talk of more skills, but I don't think that is necessary. If anything, the current skills should be developed more. Similarly to what db0 said, I think we could use more levels for each skill. However, I think that the levels should branch out. Instead of just breaking skills down into 8 specific benchmarks, you should be able to focus on the aspects of the skill which you want improved. Not just generic cooldown and manna cost, but specific things, like Snipe's range, base damage, and the damage multiplier for long distance. I don't really think this is necessary right now, but it would be a more feasable option than making entirely new skills should the need arise for more things to dump skill points into. You could also make ultimates at the end of skill paths a lot more "ultimate" given what a substancial investment it would take to get them.