Beating a Nes game with codes or game genie doesn't count. That is cheating and means you couldn't find a way to win without being a baby. Only game I can think of is Felix the Cat Nes. I am not too sure I ever beat any of the super mario games for nes. Since a lot of the levels are similar in Mario even tho they do have some variation I think I end up getting bored and never completing it. Tho, I guess you could say the same about Felix the Cat since it's just a Super Mario Bros 3 clone. However it's shorter and I think it actually does a little more variation when it comes to Power-ups. You can be a car, tank, submarine, airplane, hot air balloon and many more things.
I definitely didn't ever beat the Legend of Zelda. For one it seems like the Copy I bought online a couple years ago does not save the data correctly even tho the seller claimed the battery was still working on it. That or maybe there's a trick to saving the game? I honestly forget. Also, I had to watch gameplay videos and cheat kind of to even get far at all in Zelda. It's a complicating game with a lot of hidden things in it. I don't think anyone has ever beaten it without a guide unless they were the game creators themselves. I know someone is going to claim they have but I don't buy it because the game has a lot of cryptic stuff in it.