List of Pokemon in Unova Dex who learns Brave Bird by level up:
Ducklett (41), Swanna (47), Rufflet (59), Braviary (63), Vullaby (59), Mandibuzz (63)
I cannot fathom how Lucario is ever going to eat a Brave Bird, considering that it shouldn't be fighting a Swanna anyway (unless you're using what, Thunderpunch Lucario? o.O)
Please. Lucario may be a Steel-type, but it is also a Fighting-type and you should NOT be using Lucario, or any other Fighting-type for that matter, against a Flying-type.
As to how Rock Slide/Ice Punch can't reliably OHKO, my advice is: lrn2swordsdance
Also regarding special Lucario, the lack of any Special moves outside of the coverage-overlapping Dark Pulse/Shadow Ball doesn't do it much favours (I'd still take Dark Pulse since it comes earlier anyway and Shadow Ball doesn't really bring anything new). I suppose Psychic could work, but it's probably a bad idea to use special Lucario.