Actually, Physically defensive Rest-Talk Gyarados works very well, and shouldn't be discounted.
Nattorei is a great partner for defensive Gyarados, as after it sets up a few layers of Spikes and/or Stealth Rock, Gyarados is happy to switch into many of Nattorei's worst enemies, namely Fighting and Fire types. Gyarados can either Dragon Tail on the switch, causing double entry hazard damage, or simply Waterfall the uglier threats.
Best of all, Gyarados is actually bulky enough to stomach a hit from some of the powerful Stone Edge and Rock Slides in the tier, including Doryuzu's +1 Rock Slide (and usually OHKOing back with Waterfall). A lot of the strategies used to break the Burungeru-Nattorei core don't actually work against Gyarados, thanks to his neutrality to Payback and ability to PHaze.