Choose a militaristic Civ.
Go for early conquest. Build Barracks ASAP to gt elit units faster. Use the first leader for an army, make sure it wins it`s first fight. Build the Heroic Epic ASAP. Slow down your offensive to bring elite units to bear. Bombard with catapults to damage defenders so you`ll have higher chances to win with your elit units.
Remeber: an elit unit lost means: 1 chance at leader lost AND another unit must be promoted first so you can have another chance....
I try never to loose elite units.
Keep outdated elite attack units. They`re still good for mopping up exposed advanced attackers and hurt troops. You`ll get leaders there, too.
One more thing that may be wrong: I get the impression that when i use only one kind of troops (as I`m prone to do when playing Romans or Persians), that is I only have one type fighting, I get fewer leaders. If I have a few defenders or Horsemen fight, too, I get more leaders.
Hope this helps!