MArcomage

This shouldn't discard rares. I'm just saying...

Which part? The random card discard or the part where cards are replaced with fanatics or both?

Well, I was initially thinking only the random discard, but I believe both. Tribute, another 0-cost common that discards 3, doesn't discard rares. I don't see why Heresy should as well. Especially since Heresy could discard up to 4 cards.

I agree.

I'd like to make it where you can specifically choose a card you don't want to be discarded after playing this. It's very annoying to have this make you discard Death before dishonor.

The effect doesn't match the description any longer. The description needs updating.

Do you mean it should be something like:
Select a card to discard.
[blabla]

I've noticed this card is replacing self sometimes. Is it random whether is there any condition making it happen?

It's random - it can replace self though.

This card used to be very useful in combo with old Death before dishonor when Zealot was OP as hell. After Zealot nerf this card lost big part of its power, but up to 3 potential Zealots in hand isn't bad by any means. But Death before dishonor rework buried this card. I mean, yes, you have 3 Fanatics. What you gonna do about it when you can't upgrade them?
I suggest to rework Heresy and return a part of Death before dishonor effect to this card.

Heresy
Common, (Holy, 3G/1R - unnecessary changes which can be done)
If # of Fanatics in hand > 0 replace all Fanatics with Zealots
Else replace up to 3 common cards in hand with Fanatics

What do you think?

Fanatic it's not so bad for a common, but yes, it's not so interesing to make me use one turn, one common slot and 3 commons in hand just to have three of them.
but heresy is still a common card, so I don't think it should upgrade all fanatics in hand.
I suggest:
If # of Fanatics in hand > 0 replaces one Fanatic with Zealot
Else replace up to 3 common cards in hand with Fanatics

I think this card should be able to replace holy cards and instead shouldn't be able to replace frenzy or soldier cards, matching to the changes of the keywords of the fanatic.