Yeah, they're insanely tough, and have powerful movesets. Only way to really roll them without any care of concern, is getting a team up in the mid 70's to 80's. At that point, you can just wipe the floor with them.
Now that you've beaten the Elite Four, the Trainer I mentioned; the Fisherman, now has two Gyarados sitting at level 53. EASY for Experience Farming--toss on a Lucky Egg to your lead, and the Exp. Share to a low level if you want them getting up, as well as gaining some of the EVs--each Gyarados, without Exp. Share, yields 3900xp with the Lucky Egg being held by your lead. It splits it to half with the Exp. Share being held by another 'mon.