Carrying on from the small point I made below, so much of storytelling is about the way you choose to tell things, rather than the core story. There are different stories, but only on quite a surface level, of the details of people's lives, of the mechanics of the plot. In some genres, most obviously crime fiction, there is really only one story at the heart of the whole genre. In this case, the hero comes into contact with a mystery of some sort, and solves it.
So how is it possible to go about being different? Well first, it doesn't have to be completely different. We've just established that some things are going to be the same. And some genre essentials are probably going to show up, either in original or messed about with form. It's a bit like playing the blues. It's been done. You know it's been done. And it doesn't matter.
But that doesn't illustrate my point about changing the way you tell things, so I thought I'd take an example, in the form of my completed comic fantasy novel Court of Dreams (which hopefully the agents I've sent it to will like).
The thing is, it didn't start out as a comic fantasy novel. In fact, elements that appear in it, such as the idea of how the fantasy world worked, came in the course of writing a piece of urban fantasy that just didn't work. In fact, I had two very different attempts at writing the same piece in that style, the first of which gave me what turned out to be a basic plot to make fun of (Main Character turns out to be related to assorted supernatural creatures, has to spend time running away from farie queen plus her daughter), the second of which fleshed out some vital details (such as figments, my handy swiss-army-knife like dream people, who aren't much fun in the first attempt, but provide endless opportunities to do odd things once you make the effort).
Now, let's face it, there's not much there. There's a very basic idea, which looks a bit daft (as all ideas do if you strip them down enough. Waiting For Godot: two tramps wait for their friend, who doesn't show up). There are a couple of largely atmospheric points, a few character names, and a growing sense that me attempting to be serious just doesn't work.
It's at about that point that I thought 'why not?' and decided to re-do it in possibly the silliest style I could manage. And it worked. More than that, it worked brilliantly. Why did it work though? It's not a different story. In fact, looking back on it now, it is in fact almost exactly the "serious" urban fantasy effort I abandoned in the first place, as far as plot goes. Really, the only differences in terms of the fundamentals are flipping to a male main character and changing the dynamics of the chase by introducing Grave, the Court's greatest, and most forgetful, hunter. Now unless we're saying that all you need to do to vastly improve a story is introduce an eight foot, hairy bloke in a brown overcoat, I'm not sure that this is what made the difference. (Though to be fair, Grave did provide a wonderful target for all sorts of things I couldn't do to my main character).
Instead, I suspect it has a lot to do with the idea of writing in your own literary voice, rather than as you think you ought to. More than that, it's about writing what you really want to, rather than what you think you ought to. I'm sure that's not advice that sits well with the whole analyse the market approach, but consider this: whatever you've decided you ought to write because the market wants, someone else is also writing, and they are doing it better, because they care about it. A rather blunt point, unfortunately, but I hope a valid one. If you write what you really want (or rather, given that this is about style, how you really want) you will almost certainly produce better work. And, in my case, funnier work.