I have an Salamence with the Choice Band build from Smogon.
Salamence@Choice Band 252 Atk/ 252 Spd/ 4 HP - Adamant.
-Hidden Power Flying (I have Aerial Ace, I couldn't be bothered to get the correct IV's for HP Flying, I reckon it works just as well, it also takes down Double Teamers pretty well.) Aerial Ace - TM40, from the 5th Gym Leader.
-Earthquake - TM26 can be Picked up/I think I found one in the Aqua Base. (When you do get it, make sure you clone it, as they're hard to come by)
-Rock Slide - Battle Frontier.
-Double Edge - Learns it at level 93.
The last move can be replaced with Brick Break or Flamethrower, depends what coverage you're looking for.
Via Battle Points. You gain Battle Points from fighting at each of the Facilities, if you've not got a team together, it may be just worth going through Battle Factory as you don't have to train your own Pokemon, but it can be quite difficult.
I'm not sure if Fly would work well with a Choice Band Salamence, as the Choice Band only enables you to use the move you used first, and Fly is a two turn move, they could easily get a Double Team in whilst you're in air, plus Fly already has 95% Accuracy, meaning if they Double Team you could be in trouble.
You could use Fly if you change the item on Salamence to something random like King's Rock I guess, a chance to flinch is always helpful.
If anything you could get rid of the flying move altogether and just use Brick Break, but you won't have any Double Team coverage, or Fighting coverage. Something like Heracross would be 1HKO'd from a AA.
I know its not a problem, I'm just saying if the time calls for a flying move, AA would have been a sure-hit, 60 power STAB'd in one turn, imagine if the enemy used Rest or Double Team, or Dig/Dive whilst you were in the air. But as you said before, its better than nothing.