Actually, Ice Beam's not a terrible, terrible idea. Un-EV'd Naughty Feraligatr will score a solid 2HKO on the Specially Defensive version of Tangrowth and KO the dragons (Yachechomp cries, actually, at how awesome Ice Beam is with Feraligatr's boosts). Nattorei still cockblocks though, but Ice Fang was doing practically the same damage anyway and has slightly less accuracy. :/ Might be preferable on the Agility set.
Hm...I was wondering how much speed an Agility set really needed. At 252 and Jolly/Naive, it's outspeeding everything up to Adamant Doryuuzu with Sand Throw, and...it loses quite a bit of power but it should still be enough to punch in a few holes and clean up at the end of the game. At 252 and Adamant/Naughty, it outspeeds everything up to Deoxys S, so it has enough power to really kick around stuff and is still fast as hell.
But if I decided I only wanted to outspeed Scarf Hihidaruma by a point, I could just use 100 Speed EVs and invest the rest in SAtk--it has a shot at a 2HKO on Physical Skarm with Ice Beam (definite 2HKO with Stealth Rock)--or HP.
Someone posted below me about a solid 2HKO on Celebi. That's it, this thing is pretty impressive. It's battering tons of things in one to two hits with no DD attack boost, which is kind of cool. Physically Bulky Waters check it, but they really can't do anything back 'cept maybe Boiling Water, and lol Burunkeru please don't switch him in, he might absorb Waterfall but Crunch will hurt. Nattorei, on the other hand, can take a hit and actually do something back, and Porygon2 also does a hell of a job with buffering his defenses with a Prevo Stone, tracing Encourage and boosting Thunderbolt.