I like the idea of being able to get some help with improving skills (my current character would certainly benefit from any and all combat training). Balancing this may be tricky, though.
- In addition to a higher cost for higher level training higher levels of training should probably require higher levels of trust, so you'd have to build up a reputation with the potential trainers (and/or their villages) for them to accept to train you. That would prevent you from just traveling around the world to seek out the masters to gain mastery in a comparatively short time. Instead, you'd have to spend a considerable amount of time while concentrating on only a few skills (the ones available in your vicinity).
- Training would also need a cool down similar to the quest intervals, where the cool down period is used to practice what's being taught.
- Training quest rewards should be more valuable than trainer training, though, and one way to achieve that would be to allow trainers to train you only up to the level below their own, so grand mastery would require quest rewards and/or actual practice.
- Offering trainer services might be made into a new quest reward.
- Trainers should probably be identified through talking to villagers, as everyone skilled in a trade isn't necessarily interested in or capable of training others. It could even be done such that villages would only reveal trainers and offer training to people they have a sufficiently good relation with, so you couldn't just travel around to locate all the trainers and then set up a training resettlement strategy, but would have to resettle first and then find out what becomes available over time.