@Buckert: You hopefully haven't purposefully overlooked my answer.
A Gyarados with Avalance is impossible to get outside of the 4th gen, so is Sucker Punch Hitmontop (for that matter, any Tyrogue evo with Sucker Punch). Also, when you do not have access to Focus Punch in the 5th gen yet, you may take a look at Breloom.
Avalance, Focus Punch and Sucker Punch are moves you only can obtain freely in the 4th gen.
Avalance: It's Gyarados's strongest Ice move. It is a consideration worth for Rhyperior, Feraligatr, Ursaring, Tyranitar and Rampardos, but note that everyone of them also has access to Ice Punch. If you like more exotic stuff, try the physical tank of a Winter Suicune with Avalance and Extremespeed when you don't shy away from Wondercards. And Regigigas, when you don't mind people laughing at you. Sumpex, too, but it has access to Avalance in the 5th gen through breeding.
Focus Punch: Well, the most notable examples are Tyranitar and Breloom. The latter one need not to be in the 4th gen to learn it, thanks to 5th gen breeding. There is also Blissey-Boxer Palkia, but you should look for another nature and a close hexa-flawless spread in that case.
Sucker Punch: Hitmontop, Hitmonlee, Skuntank, Shedinja and Slaking. Shiftry unfortunately needs the Ability 0 for Chlorophyll. And there is SD-Celebi, but Wondercard only.