I think to fix the system we need to at very least change leveling to a total skill XP requirement, not a total skill levels requirement.
Additionally though there needs to be some way to increase stats without grinding out a certain task over and over.
I think the system for leveling up weapons in Warband could be a good starting place. You got points in your One Handed, Two Handed, Polearm, Archery, Crossbow, and Throwing skills primarily by using those different types of weapons in combat. However, you also gained a few points to spend on any of those stats when you leveled up, allowing you to get better at using a certain weapon without grinding use of it. This wasn't unlimited though. Higher levels took more points and there was a cap, set by the Weapons Master skill, on how much you could manually increase them.
This would be easy to implement. Just give people some bonus XP whenever they level up that can be given to any stat, and then increase the level up cost for the next level by the amount you give them. Just don't let people use this XP on stats that have hit their cap.
Alternatively, you could implement a reading books or tutoring system where we can pay money to buy books or hire people to increase our skills whenever we're resting. That way if we don't want to grind a specific activity to increase a skill, we don't have to.