As an example, if you attack with a Water Elemental (3/6, freezes enemy any character that it hits) a hero that has 4 armor, will he be frozen or it needs to do health damage to be able to freeze?
The water elemental just has to deal damage to a character for this to work. So armor doesn't protect you, but e.g. a divine shield would protect your minion from being frozen.
This used to work differently early in the beta, but was changed at some time. From the patch notes:
Water Elemental (Mage) will now properly freeze armored heroes as intended.
He will be frozen, you just have to hit the charachter.
"The Water Elemental causes a Freeze effect on any character he damages, causing them to miss their next attack. This includes minions and heroes, making him quite effective for preventing equipment-using classes from putting their weapons to good use.
Note that Water Elemental only freezes characters it deals damage to (including reducing hero armor). Minions protected by Divine Shield will not take damage if attacked by the Elemental, and therefore will not be frozen." (source: http://hearthstone.gamepedia.com/Water_Elemental)
Also have a look at this link for more information about the freezing.