Well first of all, you need to exchange friend codes with the person you want to battle. To find your fc(short for friend code) just go to your main items in the bag and find your Pal Pad. After you have yours friend fc you need to register it in the same Pal Pad item.
Now you have two options: take the team that you want to battle with or put your team in the battle box*, which you can do from the in game pc. Now that you have that ready go to the nearest pokemon center, go up the stairs and talk to the lady in the middle. She will take you to a place where all the people you have register in your Pal Pad will appear if they are also online. Just pick the person you want to battle with and choose the battle style of your preference!
*= in gen 4 there is no such thing as the battle box, so you always need to take your team as your party.
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.
Would anyone here be able to get me an Imposter Ditto with a flawless HP IV? Not as fussed about the nature, something like Relaxed or Sassy would be fine. If anyone can help me out, I'd greatly appreciate it!