I'm of the firm belief that musical clichés are good. Without clichés the listener can get lost. IIRC, Pat Metheney's "Zero Tolerance for Silence" CD is entirely free of clichés. I just can't bring myself to listen again to confirm my first impression.
Even the stuff that was supposed to be cutting-edge when it first appeared is full of clichés. Bop, fusion, various metal subgenres and prog may be technically demanding, but they wouldn't be identifiable without their respective clichés.
Take this with as many grains of salt as you consider appropriate: I think the secret to not "sounding" clichéd is to draw from sources with which your audience isn't necessarily familiar. History is full of examples of how well this works. The British Invasion adapted and imported American folk and blues that virtually none of here in the US knew. The San Francisco sound of the second half of the 1960s was basically folk music presented in a way that the listening public could never have anticipated. Each succeeding era of classical music built upon its predecessor; composers made a conscious effort to break the old molds, but still retained enough familiar clichés so as to not alienate their audience.
One thing I find really helpful, as far as (giving the impression of) avoiding clichés, is to not try to duplicate other players' material. Let's face it, a lot of guitar playing depends upon muscle memory; once you get someone else's music into your fingers, it's gonna come out... That's not to say that I won't learn someone else's music (although I do that now far less frequently than I did in my early days of playing the guitar), but rather that I'll learn it on my own terms. I won't sit down with a recording and try to copy the form, the key, the sound, even the notes. Rather, I'll put something together based upon my memory of a piece of music; I'll pay attention to the parts that really caught my attention, and take considerable license with the rest.
Now, there's two ways to look at that. I could say that I'm taking creative license, or I could say that I'm too lazy to learn the song the way it was written. In reality, both are true. But in my defense, I made a conscious decision back around `74 to try to find my own voice on the instrument, and I haven't attempted to play a song note-for-note ever since. I believe that was the right choice for me, given the limited time that I've had to actually play the guitar. (Keep in mind that I stopped playing for about twenty years, and came out of "retirement" in `99.)
But I also have tons of respect for musicians who do play other peoples' material and can make me sit up and take notice of the fact that they nailed a song just the way I remembered it. I believe that can be far more difficult than what I do.
So, um... Yeah. Maybe it does all come down to my being lazy... :)
I'll let you in on a little secret... I used to be read quite a bit of science fiction. One of the most inspiring pieces I ever read was Heinlein's "Tale of the Man Who Was Too Lazy to Fail", found in "Time Enough for Love". The message of that story was very comforting to me after having been subjected to over a decade of being harassed by teacher after teacher after teacher for being an "unmotivated underachiever".