Here are Pokemon that are technically NFE, but so powerful as they are not allowed in typical NFE battles. The "NFE Ubers" if you will.
Chansey: A common sight even in Ubers, Chansey is one of the best walls around, and definitely the best defensive NFE, all thanks to eviolite, which makes its special defense absolutely riduclous and boosts its poor defense to great levels. Even before Gen V Chansey remains a great special wall and support Pokemon thanks to its massive HP and the ability to provide wish support, stealth rock and reliable recovery in Softboiled.
Gligar: Similar to Chansey, Gligar rose to the upper tiers thanks to its Eviolite boosted defenses, and became a premier defensive wall in UU. Reliable recovery, no issues with Toxic, hazards and the ability to take any fighting move make it very popular. Even before eviolite, Gligar's great BST of 430, great base 105 speed and cool base 85 speed make it both a quirky and highly useful support Pokemon that can also spam powerful Earthquakes with its good base 75 atk.
Dusclops: Again another eviolite boosted Pokemon, but Dusclops actually surpasses its evolution in walling capability. Base 130 defenses, further augmented by eviolite, make it ridiculous. Even before Gen V, Dusclops was a great wall with a great defenses and a handy spinblocker.
Scyther: Just going by BST, Scyther already seems overpowered. Base 500 total, 110 atk and 105 spd make it an offensive powerhouse. This isn't even counting technician, which gives it a powerful STAB Aerial Ace and Bug Bite. A boosting move in Swords Dance and coverage in Brick Break make scyther an offensive threat even in the middle tiers, let alone among NFEs
Electrabuzz: Similar to Scyther, Electrabuzz has a BST equivalent to Alakazaam and has a movepool that makes most Pokemon jealous. A single weakness to ground makes it decent defensively and base 95 sp atk and 105 spd make it an offensive powerhouse. Its STAB, Hidden Power and Focus Blast are typically all the coverage it requires.
Magmar: Electrabuzz's counterpart is a similar offensive beast. Base 95 atk, 100 sp atk and 93 speed? Ludicrous. Add on a great mixed attacking movepool including Psychic, Fire Blat Thunder Punch and Cross Chop make Magmar a potent offensive threat.
This is NFE OU
Boldore: Boldore has great base 105 atk and 105 defense, further augmented by eviolite. It gets all the coverage it needs in Rock STAB, Earthquake and Explosion, and can also set up Stealth Rock. It is also a good response to Yanma, as thanks to sturdy it can always survive a hit, and retaliate with Rock STAB. It also is a great trick room sweeper.
Charmeleon: Two things make Charmeleon a monster: good base 80 speed and Solar Power. Under the sun, Charmeleon can plow through unprepared teams and be a severe pain to prepared ones.
Grovyle: Base 95 spd and base 85 sp atk, Grovyle is a great glass cannon. Its special movepool is pretty much limited to Grass STAB and Hidden Power. But don't worry, with swords dance and a wide physical movepool, it can also run an effective physical set. And then of course there's subseed.
Gravaler: Basically a Rock/Ground Boldore, It has a slighty more diverse moveppol including double edge and focus punch and STAB on Earthquake, but also has six weaknesses, two of them double.
Yanma; Its great. Good base 75 sp atk and 95 speed and great abilities in speed boost and tinted lense make Yanma an offensive monster. Good STABs in Air Slash and Bug Buzz and coverage in hidden power make Yanma a powerful threat.
Meditite: While Meditite seems subpar at first, Pure Power makes it a base. An equivalant attack stat of 392, equal to terrakion's, with an attack boosting nature at level 100 make this thing scary as bleep. Eviolite can also augment its defenses if need be, but just remember to take advantage of that ridiculous attack
Marshtomp: Marshtomp is may not be the best, but its quite a nice offensive tank in my opinion. Its sole weakness to grass, good overall bulk and nice base 85 atk make it an effective tank. Add on the fact it can be both an offensive pivot and defensive support and Marshtomp is quite a handy poke.
There are several good options I failed to include, among them most weather sweepers such as Seadra, Ivysaur and Weepingbell, as well the NFE starters, all of whom are viable, and the menacing Caarvanha, and those that Eeveelution mentioned. If there's another one you think I missed, I'll be glad to add it. Hope this helps.