What I do is to target the lowest level diplomats with the highest success rate. If I get lucky enough to earn 2 or 3 levels, I switch between diplomats and low level generals (0 or 1 star), princess and priests, until a reach level 5 or 6. With that level I keep my spy until a find a great general or a high level target (a good merchant, priest/imam, diplomat).
Every time I try to get to a higher level, my spy very often gets killed and I get really frustrated feeling I have spent a lot of time risking it with the less important units.
Some other advices are to mass recruit them, as you'll probably lose many of them, and at some point build the Assassin's Guild and later an Assassins Guild Headquarters to get +1, then +2, on assassin's skill level in that town.
Tips are shown here