Just building spies and keeping them in your cities without training them works pretty well. As long as there is a brothel or higher order derivation in the city where the spy is parked, he should pick up some nice members to his retinue. Also building spies from cities with Thieves' Guilds (which are not hard to obtain by any means) also give that extra push to spying skill so that they can root out the bad spies without resorting to any nasty work.