Thanks for the replies.
Just take the region from them, remove the entire garrison and destroy every building that gives public order bonus, while raising taxes to very high. Should become rebel city in no-time!
Some times, when I do that, the province revolts to the faction I just took it from... Why is this happening? More important, how can I tell if the province will revolt to rebels or not?