Here's the problem I see with Guts and Quick Feet: His Attack isn't high enough and he doesn't have a strong enough physical STAB. Hariyama has base 120 ATK and Close Combat; not to mention he can use Fake Out to set up Guts. Heracross has TWO base 120 STABS in Close Combat and Megahorn. Swellow is sick fast and has STAB Brave Bird and Facade. Ursaring has STAB Facade coming off of base 130 and access to Close Combat. Feraligatr has base 105 and Waterfall...meh. Oh yea, and Aqua Tail...yay.
Swift Swim gives him something over Gyarados, but Kingdra still outclasses him in Rain since he's neutral to grass and electricity. He can't even claim superiority with Swords Dance and priority since Kabutops is the exact same way, but deadlier and has access to STAB Stone Edge.
Intimidate helps everyone, so that's a good choice. Come in, reduce their attack and Dragon/Swords Dance up. However, big brother Gyarados is tough competition since he has an immunity and more resistances, so he can set up easier. Ice Punch is better than Ice Fang, though.
Rough Skin could help him get some KOs on physical attackers. It's not a bad ability and his only competition is Sharpedo, who has base 40 defense. Feraligatr could make great use of this because of his good bulk. Of the 5 you listed, I like this one best. It's actually probably the best other ability he could have.