My favourite Nattorei set:
Nattorei @ Leftovers/Rugged Helmet
0 Speed IV
Brave/Relaxed 252 Def 252 Atk 4 HP
Curse
Gyro Ball
Leech Seed
Spikes/Toxic/Power Whip
This set takes advantage of Nattorei's abhorrent speed in combination with its applicable ability. Not only does its speed and attack create a unique late-game sweeper, but a defensive physical wall with a special flavor. Curse + Gyro Ball allows Nattorei to maximize its properties primarily by raising its attack and dropping its speed. Meanwhile, the defensive boost combined with an already solid defense stat will cause hell for all physical attackers, especially when contact moves are involved. Spikes and Toxic offer additional support in chipping down both incumbent and incoming opponents, while Power Whip takes advantage of a powerful STAB move. Leech Seed in combination with either Leftovers or Rugged Helmet will tear down the opponent as well while healing Nattorei's considerable demeanor. It also allows Nattorei a first-turn move incase a switch-in forces it out. Thunder Wave will barely cripple it, especially with the motivation to drop speed and with the support of Leech Seed. Toxic and Leech Seed are no problems either, and even if Taunted, most of the time Nattorei can wreck with even an un-setup Gyro Ball or Power Whip.
Mach Punchers for the most part, despite their 2x offensive power, will still have issues with this Nattorei. The classic "Hax" Jirachi will faces issues as well, as even if it causes consecutive flinching, Nattorei is more or less likely to survive if not hit it back. Fake Out-ers will cringe when they hit Iron Thorns. The combination of all these allow Nattorei to effectively switch in to any predicted Physical Contact moves and wall, stall or sap away at the opponent.
Disadvantages: Firstly, in my experience, Nattorei has never taken well to special Fire attacks, especially in lieu of the (unreleased) Shadow Trap Shandeera. Thus, I personally do not invest in it and instead maximize the focus of this set. Otherwise, one could invest the EVs into Special Defense or opt for an Occa Berry (in the future, Shed Shell). Nattorei still has the stats to be an effective Special wall, barring any fire or fighting attacks running around. Other bulky and slow Pokemon prove problematic to Natty as well, especially if they tote around special attacks. Porygon-2 especially with Evo Stone will use special attacks to damage Nattorei considerably. Taunt and Trick Scarf have the potential to completely thwart this set. Thus, Nattorei has quite a series of potential throwbacks, so one should take care to eliminate these by the time they plan to use him for offense.
Addendum: Shed Shell for Magnezone, Gavuntula, other trappers et al.
Some moves I'm not fond of:
T-wave
This defeats the nature of this set, allowing less opportunity for the opponents to be hurt by their own contact moves, and slows them down which lessens the power of Gyro Ball.
Protect
Nearly the same reasons as above, although more useful if Leech Seed is already set up.
Power Whip
Although powerful, it lacks accuracy and Gyro Ball is by far a better offensive option. Regardless, it still has many opportunities to be extremely useful, especially with bulky waters.
Stealth Rock
Because Nattorei can sit around for so long in the correct circumstances, Spikes is more opportune.
How NOT to use Nattorei, in my experience:
He absolutely hates Special Fire attacks, and I have yet to see him survive. Even if one maxes Special Defense, special sweepers with access to any sort of fire move will most likely OHKO Nattorei regardless.
His late-game nature, predictability and dislike of Taunt/Trick means he does not work as a lead.
ADDITIONAL NOTES: I owe credit to this set entirely to Hex. I freakin' love it, makes me enjoy Nattorei more, and he's amazing for seeing all these which I am basically just reiterating.