Ulykus
You can get your fame down easily by revoking citizenships and/or religions you don't have.
But you need to know that city guards in capitals will kill you on sight at -40.
I tried that, but it's not possible. They only tell me: "You are not a cititzen. I have no time to waste." But I dont lose fame.
Anyone has got experience what's the most efficient way to lose fame? :D