Pretty cool idea. The bonuses might be a bit overpowered but I get the point and I like it.
It seems like it wouldn't be that hard to implement either. We already have quests that are based on your skill level. We could just had trainers give a quest where they just talk to you and reward you with the bonus item when you hit certain milestones.
Maybe instead (to avoid coding a bunch of new bonuses) each skill could reward higher quality tools. Like rock picks with 75q, 100q, 150q, 200q, and 250q for the levels listed above. Cooks could gradually receive better tools and at higher levels receive their own kitchen equipment (pot, bowl, iron skillet). Alchemists could get better stirrers, and eventually their own mortar and pestles. Etc.
We could even make a quest for each one if we wanted. Like "Hey, you're progressing well in this skill. Tell ya what. If you go fetch my new [tool] from Harnquist/Jirosh/whoever, I'll give you my old one for free. What do you say?"