Have any loveable, harmless, friendly NPCs? Not someone major or plot important, but someone the PC's have come to recognize. You know, the one guy whose voice you do at all the inns (even if it's not really the same guy). Although tropey, I've found one of these to things works well:
1. Have the church execute him. Publicly. When he is technically guilty of something rather minor. Make it so the PC's can't save him. e.g. they only just got to town and it happened two weeks ago.
2. Have him refuse to associate with the PCs for reasons related to the church. e.g. "I'm sorry. I can't talk to you anymore, warlock."