Oddly enough I recently started a game with this exact same intention - spreading heresy as far as possible.
Becoming heretic is surprisingly easy - it will commonly follow on from the 'sceptical' or 'excommunicated' traits. Good tactics are to church-unfriendly religious law (then tell the pope to get lost when he complains), and promote the 'religious flexibility' advances (this encourages heresy in provinces).
Loyalty problems mean you pretty much have to be prepared for the heretic King to run his kingdom by himself - a large personal demense with few/no vassals (though some friends may stay sympathetic if heavily bribed). The biggest problem is actually in court, as you can't bribe courtiers to like you. My heretic rulers tend to run the government single-handedly too - no court is preferable to a rabidly disloyal one (there are nasty events attached to disloyal advisors, especially the steward - it is more cost effective to remove / assasinate them than have them steal your money). If you end up with no vassals and no court (as I did), then loyalty is no longer an issue!
Once you've established your one-man despotism, the second problem is defending it from agressive neighbours. Fortunately heretic provinces get 10% income boost, which increases manpower for fighting. You will still need an easily defensible region, with lots of rich provinces next to each other to create a powerful personal demense. In my game I chose the island of Sicily for this (hold all 5 provinces and you can drive invaders back into the sea)... though there may be better areas?