That said, it could be interesting to randomly (and secretly) give the character some special power. And then as part of the game, they have to discover it and figure out how to unlock it...
I agree with this - if all your characters start off the same (or nearly the same) and yet they have some hidden yet-unlocked abilities that are randomly given, it would be interesting to explore those abilities and their extent.
Much in the way that exploration of the world is interesting, the exploration of your character's abilities could be interesting, and probably enough to be a game in of it self.
Trying to imagine a more specific example of this (of course this is only my view and only one way that this can be done):
Say you give the player an ability to 'focus', in a very standard press and hold button X way, and your character had the hidden ability of telekinesis.
If that character focused on a small enough object (defined by the 'mass' of an object, say a vase) the vase would wobble slightly. Further attempts of 'focusing' on the vase would yield more control over the movement of the vase, until eventually your character was able to pick it up.
This effect would only manifest itself when initially focusing on a small object. If you started a brand new character with the 'telekinesis' hidden ability, and focused on a large rock, nothing would happen, nor would your ability develop further. You would only be able to lift large rocks after progressively focusing on something small at first and slowly attempting to focus on larger and larger things (e.g. vase, bucket, wooden planks, smaller rocks, etc)
By the same scheme (using focusing), say you have a character that has pyrokinesis as an ability (for lack of my imagination right now).
Focusing on that same vase wouldn't yield any results, nor would focusing on a large rock. However, if you focus on a candle, or say, a small piece of paper, you could make make it smolder/smoke, and further attempts would increase your ability to heat things up, until eventually you may be able to focus on a large rock and melt it away.
With more time and imagination, you could come up with dozens abilities, and make the player explore their character. You could have branching paths of sorts, where two hidden abilities manifest in very similar manners (focusing on a metal object would make it wobble whether you have telekinesis or er... ferro-kinesis (basically magnetic powers)). Or possibly allow multiple hidden abilities in the same character too.
As a more detailed addition to this "focusing" you could have a system where you could focus while thinking of a combination of two common elements (think http://armorgames.com/play/6313/doodle-god Doodle God) and have the different hidden abilities be revealed (only if present in your character of course) in case the player picks the right combination of things to 'focus' on (e.g. focusing on air + dirt would reveal telekinesis... sort of an odd example, but i'm shooting more for giving inspiration rather than trying to tell you how it should be done)
And this isn't even thinking about how you could possibly combine your abilities and their strength with the standard rpg level system.
As to the comment that such systems might force player to re-start the game. I also feel this way about games which have a random element.
I was thinking that one way you could fix this would be to give the player the ability to create more than one character in the same world. Say the player develops a character with water control abilities, and then starts a new character that ends up having fire controlling abilities. If the fire-character encounters some sort of puzzle or something that would require water abilities, allow the player to bring in the water-character into the fire-characters world and play there. So, basically a sort of a single-player-persistent-world, where you can only play one character at a time, but you could switch to any character you had already made (via some system of course, not necessarily freely and anywhere)
Anyway, I went a bit overboard. If done right, I think exploration of your character's abilities could be a very interesting idea!
Edit: fixed a couple of mis-types and missing words.