Another was to level without going into any town (possibly simplifying that to any "full" town with an inn and everything). The challenge with this would be to find a class with a suitable trainer that would be accessible while meeting that.
I mentioned this one, as I had heard of people doing that back in Morrowind.
How about doing Lore Master during the process of leveling? As in, each zone would have to be done at an appropriate level. This would require turning XP off and on strategically. Oh wait--you wanted challenges that made it More interesting.