Oft times, Cliches are not avoidable. and sometimes going out of your way to avoid them has become cliche in its own right. If the shoe fits, wear it. If you need to drive a nail, do not use a mag-light just because it is unique. If you run into a cliche, and it fits like a glove, wear it. Don't kill yourself to work your way out of a cliche. the Story is what matters.
The Book "Red Country" is medieval fantasy (ish) set in a western type land. The author pulled off, what basically, is a gigantic stereotype and put his own spin on it. The characters speak like they're in the west. There's wagons, pilgrims, a gold rush, indians (though they're called ghosts), and that hugely stereotypical western town with all wood buidlings, swinging doors for the pub, prostitutes and those rough crowds of men always fighting while staggering drunk. Yet this is done with men carrying bows, axes, swords, etc. It's very unique...in a strange, stereotypical sort of way. He took the common european type setting and upended it.