Contra is pretty much impossible to beat without using the code, since it was designed as an arcade game and you're supposed to die a million times, so I don't count it. SuperC, by comparrisson, was made solely for the NES and is much easier.

Time Lord! Not a very popular game, but man it's hard.

Two other games on my NES-never-beat list until recently were Mike Tyson's Punch Out and Teenage Mutant Ninja Turtles (1).

Mike Tyson is hard, but if you can get past the first 1:30, he doesn't throw the knockout punches anymore (though he's still pretty hard). I beat him multiple times including a decision at the end of the third round (hardest way to beat him I think).

I admit I had to consult some cheat sites in order to beat TMNT, but only to find which ways to go in a couple of the levels (the one with the turtle van and the airport one). The technodrome is pretty much impossible even with all four turtles with full health. I got to Shredder at the end with one turtle left and barely any power but got lucky I guess.