Train them on other factions' army stacks. Even at level 1, they have a decent chance of success, and at level 2-3 it saturates at 100%.

I had a couple of spy problems after I took Antioch during a crusade. I trained 3 of them and kept sending them against egyptian stacks and diplomats. After a few turns, they were all 4-5 stars and kicked the 2 egyptians spies out of Antioch.

Seriously, spy training is very easy in this game. Can't say the same for assassins though (or priests).