A relatively soft carbon cleaver or a Western deba -- all will get damaged as well. But repair is very easy if you maintain them with highly convexed edges. Not so with a comm hard gyuto which hasn't enough steel behind the edge and where you may expect serious chipping.
THERE I can indeed fully recommend a certain Kiwi - their 2mm thick cleavers do me good service splitting off and mincing frozen coarse grated coconut (an ingredient that makes keralan and goan dishes great when there are no decent coconuts around ).
@Benuser didn't care what the actual thickness was, but wanted to point out a type/series of cleaver - which is 2mm thick for 4/5 of the blade, rest is the Kiwi-typical slight hollow grind, which however in this case is sturdy enough . Didn't want anyone to confuse them with similar looking chukabochos that might be in the same crate at your asian grocer
(still tempted to get a yakushika-cleaver one day just for the fun of it )
Get a cheap but reliable Chinese San Han Nga all stainless cleaver. They should be a bit more durable than Kiwi too. I recently was helping to repair edge damage done to a thinner Kiwi cleaver a friend had from chopping bones
If you got a heavy duty chop block a fat bone cleaver with a tough convex edge works. I tried this at home, works best when the chop block stands like a rock.
I modified a 165mm kurouchi Shigefusa santouku to thicker behind the edge.
This knife deals with anything straight out of freezer at home and I love it - it handles any hard and dirty job a knife can see wonderfully. Moreover, it is on the cheaper side of Shigefusa; I feel everyone should have one of those at home.
Western deba. My two Tojiro westerns (210 and 240) are pretty much reserved for going through frozen soft foods with firm pressure and the weight of my body. For hacking, get yourself a cheap soft-steeled cleaver and hack away.
I remember there was a similar thread a couple months ago and the conclusion was, you should probably cut stuff up before you freeze it, or just defrost it if possible. No matter what the knife is, it just isn't ideal to cut frozen items.
Ideal (cut up before freezing) and reality (jam packed freezers that will still cause pre-cut stuff to fuse and be hard to portion. Things that don't come cut and that you want to freeze in original packaging. Ingredients where you only decide upon using them how you want them cut. Sometimes, no time to prepare stuff since you need it safe in the freezer now...)
Masahiro, at a cheap stainless line, without bolster makes a knife for frozen foods, gyuto profile, with very unique serrations, some sites call it bread knife, but it isn't. A friend has it.
Pretty cheap, I don't know how effective. He has it for fish bones, for that, he tells me it is effective