I don't think XP is necessarily "arbitrary". It's just a game mechanic that could be made so that it appears rather fluent and natural. How about the following:
* Use skill to make it eligible for raising. Skill books do the same thing.
* Play the game (rather than just grind the skills) to eventually get enough XP to level up.
* Once you've assigned the points you can go to trainers to learn the perks.
End result is that leveling up is part of the gaming experience. Someone in another thread mentioned that finding the place (quest) was part of the game experience that was now stripped away. Any old timers here remember how we used to level up in Bards Tale?

That's what I'm talking about - make these things part of the game to enjoy rather than mechanics that doesn't make sense. Time progression would be well embedded in such mechanics, of course in a way that doesn't occupy any time in real time. That being said, traveling and waiting for stores provide a fairly good time progression mechanic.
But, as we know, many players, especially fresh ones that "don't have the time to play the game" tend to call these things "tedious". It's something you do 50-70 times in 2-300 hours of game time - hardly tedious if you ask me.
One problem I have now with skill based leveling, is that I'm only using skills that are max'ed out. So I play and I play, even begun some questing. But the sensation of leveling progress has completely ceased, something that didn't happen in FONV. In FONV, as long as you "kept playing the game", you were awarded with sensation of leveling progress. It doesn't matter that much though, since in the beginning in Skyrim I felt I was leveling way too fast.