Gwynoth: im almost convinced hes supposed to die and you can't get the book by stealing it, instead and must launch an invasion. Anyone done this with JUST ZHEF? only youtube vid i found the guy failed.
Yes, it is possible. In fact it is the "normal" way of doing it.
First question:
You do know that you can have the spy impersonate one of the enemies, in which case he'll look like them and be able to enter the city?
Unfortunately though, after that I can't give any specific advice. Just this: save often. Avoid moving patrols, since they seem to be the ones who can uncover him most often, but it seemed to happen randomly; I couldn't find any specific reason on why sometimes he'd be caught and sometimes not. Which is why you should save often, and if you get caught, just reload.
Not the most pleasant of levels (but it was fairly short) mainly because of the randomness of the whole thing.