While Staraptor, Braviary and Garchomp are definitely a good choice of Pokemon, there are a few flaws.
As ThePika mentioned, while Staraptor does have a very decent Speed and Sp. Atk. , it is sorely lacking in all it's defensive skills. Unless Volcarona is OHKO'd (unlikely, even with Brave Bird) , it's almost guaranteed that Staraptor will be taken out in the next move. (For example, Volcarona with Wild Charge = Staraptor Steak.)
Again waith Braviary, it's got decent HP and Attack (which could be very potent with Brave Bird and Rock Slide (remember : Volcarona has a 4x weakness to Rock!), but it's slow. It's defenses might not be able to hold against a Fire Blast or Wild Charge.
Garchomp is another brilliant idea. It's got very good Attack, decent HP, and above average defenses. Above all, it can outspeed a Volcarona with a Hasty nature. DeadlyHaxorus29 has provided an ideal moveset as well. Ideally, Rock Slide should easily be able to 2HKO a Volcarona, if not OHKO it.
My suggestions :
Adamant (+Atk., -Sp.Atk.) / Lonely (+Atk., -Def.) / Careful (+Sp. Def, -Sp. Atk.
Leichi Berry / Razor Fang / Wide Lens
=> Rock Slide (Wide Lens for accuracy, Razor Fang for +10% or so flinch chance). /
Smack Down. I know it seems strange, but it's for those pesky Bouncers and Fly users. If Volcarona uses Magnet Rise, this can be useful.(Rock Tomb can also be used to reduce Volcarona's Speed.)
=> Earthquake/ Earth Power. An obvious choice. Can be used after Smack Down for Flying types.
=>Aerial Ace / Fly. STAB.
=> Dragon Claw / Crunch for overall coverage.
Aerodactyl is a great Flinch Sweeper with very high speed, good Attack, decent defenses, and a wide coverage.
Adamant. (+Atk., - Sp. Atk.)
King's Rock. (Extra flinch chance)
=> Thunder Fang. (flinch+ PAR chance)
=> Fire Fang. (flinch+ BRN chance)
=> Ice Fang. (flinch +FRZ chance)
=> Rock Slide. (Flinch chance)
Lugia is the ideal Pokemon to obliterate something like Volcarona. It suits every single one of your requirements, apart from the fact that it is not native to Gen V.
Lugia can outspeed Volcarona. It has 10 extra base speed.
It has slightly above-average attack and special attack.
It has extremely strong defenses. (Max. 394 Def., Max. 447 Sp. Def.)
Also, it can learn several moves that can annihilate a Volcarona with ease.
Adamant (+Atk., -Sp. Atk.) / Lonely (+Atk., -Def.) / Calm (+Sp. Def., - Atk.)
Tanga Berry. Weakens super-effective bug-type moves. Volcarona is sure to land a Bug Buzz if it doesn't die quickly.
Enigma Berry. Restores HP if hit by a super-effective move.
=> Aqua Tail / Surf / Waterfall / Hydro Pump. These aren't specifically against Volcarona, my Lugia has always had a water move for general coverage.
=> Aeroblast / Sky Attack. Volcarona is weak against Flying type moves, and aeroblast is Lugia's special move, apart from it getting STAB. Lugia can easily survive a Bug Buzz with the Tanga berry to use Sky Attack.
=> Iron Head. Taught by the Move Tutor. Smashes both Ice and Rock types. (That, and it's a pretty crazy move. :P )
= > Earthquake / Recover / Psychic / Extrasensory / Shadow Ball / Signal Beam / Ice Beam.
Sorry for such a wide choice in the last move, but the only reason I've done that is because Lugia can be strong with any of those moves. Earthquake is a favourite, and with good coverage, Recover if you're a defensive sweeper, Psychic and E-sensory for STAB, Shadow Ball against Ghost Types, Signal Beam against Dark types, and Ice Beam for the heck of it.
Well. That's it. :) Sorry for the long answer, and good luck with this!