I didn't feel like reading all these posts, so the question may have already been answered. You cannot throw Eye of Enders in superflat worlds and in worlds that have been created before TU7 (December 19th).
i have yet to test this but i have a theory. i have this exact problem but i chose to not generate structures in my map - i will test tomorrow to confirm but i suspect that option does not spawn the ender portal....but i'm a minecraft noob who has played less than a month so we shall see.
I have problems throwing mine as well. I probably started without a stronghold anyway, since I know that I disabled the option to start with villagers in the world.
But never the less, on http://minecraft.gamepedia.com/Eye_of_Ender, the first point under the "Trivia" section, it says (as far as I understand) that if you throw an Eye of Ender in a world without a stronghold, it will lead you to the place where the stronghold would have generated. So as far as I can see, not getting the option of throwing an Eye of Ender has nothing to do with a missing stronghold. Unless this only applies to PC, of course...
The console editions work slightly different than the PC in this regard. You don't get the option to throw an eye of ender if there is no end portal on your map.
step 1: equip ender eye
step 2: throw TV
step 3: follow TV
step 4: Dig
But never the less, on http://minecraft.gamepedia.com/Eye_of_Ender, the first point under the "Trivia" section, it says (as far as I understand) that if you throw an Eye of Ender in a world without a stronghold, it will lead you to the place where the stronghold would have generated. So as far as I can see, not getting the option of throwing an Eye of Ender has nothing to do with a missing stronghold. Unless this only applies to PC, of course...