If the developers can't mess with the length of experience needed to gain a level, they could always expand the breadth. What I mean by that is they can allow the acquisition of unique lore through side quests which then allows characters to direct their development in ways they couldn't via the main plot. By doing so, they can add to the replayability.
For example, a side quest could allow access to a rare scroll of swordsmanship that adds a unique 'talent' to the available pool. The characters will still need to level up to add the talent, but at least now they can build their character out along a slightly different path. Possibly there could be several such acquirable talents that are linked together -- gather all parts of the Ancient Art of Swords manual to master the new path.