One twist on experience I enjoyed was Fable's system. Enemies dropped four kinds of experience: General Experience, Strength (i.e. physical) Experience, Skill (read: dexterity) Experience, and Will (magic) Experience.
Experience gets spent on skills of your choice to acquire them or level them up. You can only use Physical Experience on Physical skills/abilities, and only use Magical Experience and magical skills/abilities, and so on, but can use General Experience in any category.
Enemies drop General Experience and also other experience types depending on what you use against them when killing them (e.g. they might always drop 50% general experience, but the other 50% will be mostly 'Will' experience if you used alot of Will skills while killing them).
One question I'd suggest you ask yourself is: "What am I trying to achieve/encourage?"
Are you wanting something new to serve a particular purpose, or is it just a gimmick?
For example, another thing I like in games is when you can find ability points or stat points in the world itself, which encourages exploration by acting as a reward. This can be the exclusive way to level, or it can be in addition to other more common ways.
Examples of this include:
Quest 64 allowing you to find 'wisps' which basically act as instant level-ups. This was fantastic, and encouraged me to observe and explore the environment more. There were about one hundred wisps in the game.
Paper Mario allows you to find 'power blocks' that instantly level up one of your allies. Each ally can only be leveled up once, until you reach a specific point in the game, where each ally can be leveled up a second time. These make your allies alot more useful in combat. There were about 20 of these in the game.
King's Field allowing you to find elemental 'crystals' which instantly give you a new skill of that element type (i.e. the 3rd fire crystal you find gives you the third fire skill, regardless of what order you got the crystals in). There were about 20 of these in the game.
(Note: The fewer there are, the more excitement you have when finding one)
Other games use leveling to gate the player. "Leveling up" (in a more abstract sense) acts a reward for defeating a boss or beating a level.
Examples of this include many platformers like Mega Man and Metroid (using abilities and equipment as "levels") and Banjo and Khazooie.
Instead of exploration giving you the reward, the reward opens up new routes of exploration.
In Banjo and Khazooie they are both true: You find (exploration) the NPC and pay (money can be thought of as experience found via exploration) him to teach you a new ability (your level up) which lets you navigate the terrain more (leading back to exploration - it's a loop). Most players won't think of these as 'leveling up', but they are spontaneous growths of power that enable you to overcome in-game challenges, so in an abstract sense, they are leveling up.