The thing about Feanor is that he was one of the most powerful of the Noldor to ever walk Middle Earth. While he didn't have established spellcasting powers, he was considered the most learned of the Noldor and basically the pinnacle of their race:
"For Feanor was made the mightiest in all parts of body and mind, in valour, in endurance, in beauty, in understanding, in skill, in strength and in subtlety alike, of all the Children of Iluvatar, and a bright flame was in him. The works of wonder for the glory of Arda that he might otherwise have wrought only Manwe might in some measure conceive." (The Silmarillion, Chapter 11, p 115.)
[yes, I have the book at work

]
Now the thing is, most of the lords of the Eldar, such as Finwe, Feanor, Finrod Felagund (who did display some rather impressive magical ability) and Abu Thingol were considered to be very powerful, although this was generally represented as just being tougher, more intelligent and greater in martial prowess than anyone else. But generally speaking, the Elves were just plain magical in nature. Not only that, they were effectively immortal and had a lot of time to become learned and proficient. Beyond that, the Noldor actually lived alongside the gods (the Valar) and learned directly from them.
However, once the Noldor came to Middle Earth, the Valar hid Valinor and the gods had very little contact with the Children of Iluvatar after that (except for Melchor of course). Once humans came to Middle Earth they seemed to be pretty tough themselves, and while not in the same league as the Elves could definately hold their own (I'm thinking Beren for example).
So, back to your situation. You could go the route of having the Gods be close at hand, but I'm thinking they might overshadow the PC's. So I'm thinking have the gods at a distance, and possibly even have them have very little (or no) interaction with the world and it's people. Also, don't build the campaing world "in the ashes of a once great empire" or any such thing. Set it in a period of time when there haven't been any mighty empires or kingdoms-yet. Let the players set the events in motion that found these mighty kingdoms, or even establish them themselves. I also think you have to make the PC's significantly more powerful than any of the common folk of the land *. Now, you can do this through high ability scores, high levels, whatever. But make them respectfully powerful. There should also be some high-level NPCs, but not so high they outshine the PCs. Top it all off by giving the campaign world one powerful evil bad guy that the PCs work to thwart (and eventually do) and I think it will be pretty epic.
Now, as far as the rules go, I'm thinking you should take a look at the Midnight campaign setting. I don't have the book myself (yet), but judging from what is said on the boards here I think the classes in that setting would be pretty good for what you are looking for. They represent a low-magic setting but give the PCs inherent abilities that let them accomplish great things (maybe you Midnight fanatics can jump in here and help me out

). Now, you'd probably don't want to take the Midnight story line itself, as from what I gather Izrador is a pretty tough cookie to take down and the setting is pretty dark (although heroic in it's own way), but I'm betting you could use it as a basis for your own setting. Make the setting a little more hopeful, set it in a brand new world, and give the PCs the ability to mould the world and I'm sure you'll get the legendary campaign you're looking for.
* [edit] I'm not saying you have to make the PC's +15th level or anything, just so long as they and the other major NPCs are much more powerful than the common folk. You could do this under 10th level I'm sure.