I can't say I've played all puzzle games in existence, let alone all games with puzzles in them. But I only remember one about whose puzzles one could say they were all always placed at the one and only appropriate point in the narrative and that they contributed immensely to it.
What I mean is that when the designers of most games insert puzzles (or rather, "specific gameplay sequences") at certain points in their story, their goal is to challenge the player. And that's it. Maybe because the story requires it at that specific point in the game, maybe because it gives the gameplay rhythm.
Take Half-Life 2, for example, and give me one example of a puzzle (you know, the physics ones) at some point in the game which couldn't have been replaced with another one, due to the story requiring that specific type of gameplay at that specific time. I know that in the latter half of the game, the puzzles require the Gravity Gun and can't be done without it, but the gameplay is pretty much the same: grab->put down, grab->throw.
The same applies to almost all games, where the aim of a given bit of gameplay is always either to give the player a gameplay bonus or to allow them to move on in the story or more rarely, as in Deus Ex: HR or LA: Noire, to reveal more about the depths of ths story.
On the other hand, in Braid, the gameplay and "story" are tightly interwoven. The first chapter is supposed to be "forgiving" and about innocence and so is the gameplay. The chapter with the ring is about finding comfort in the presence of someone dear, all the while knowing that their companionship is a burden (to someone as ambitious and driven as Tim), and the gameplay is a perfect translation of that. The same applies to the other levels and even to the epilogue.
Jon Blow himself said about his game design experience with Braid that it was like sitting in a gold mine and scooping nuggets of gameplay, examining them from all angles (or something along those lines, was it in Indie Game: The Movie?). That's the phase you're currently going through, it looks like.
So I what I would do if I were in your case, where you have a unique idea and you'd rather sit in the gold mine and scoop nuggets than write a story, is do precisely that, do this job of scooping as many gameplay nuggets as you can. Once you have something to say, a message to shout out, then you'll write a story with these two constraints: the message and the gameplay. They will be unrelated enough that the story can accommodate them both.
Take, for example, this painting (the medium) that depicts an old Middle-Eastern king killing his servants, horses and dogs, bringing his world down with him as he is losing a battle and his palace is assaulted (the story). It's about grandiose decadence and egotism (the message).
We could imagine lots of different works of art with the same message. For example, imagine a scene in a movie about a corporate CEO who in the end burns entire bags of bank notes in his condo as the tax administration/feds/IRS/what have you are after him.
You can always write a story that adapts to your medium and message of choice.
Edit to answer the asker's comments:
So you have a gameplay you like as well as a story you like. You would like to develop both further, but doing so would mean having to make sacrifices on the gameplay end or on the story end when comes the time to merge it all into an actual game.
One solution could be to work on the story first and use it as a constraint for the gameplay, which would only serve as the medium for it and, in your creative process, would always come second. Another solution, the converse of the first, is possible, where you find as many variations on your gameplay as you can and then see what can be done with it it terms of storytelling, hoping that you can build your original story around these gameplay elements.
All this cranking of constraints into others looks painful.
What I'm suggesting is that you take a good look at your story and try to pinpoint exactly what makes you like it in the first place. What, in its substance, makes you want to tell it. Extract that substance, forget about the details of the story like the setting, the names of the characters, their looks, the duration of the story, forget that it's about human beings (it could be about animals!), forget all of this and look at its substance, its deeper message, somewhat like I did (or tried doing) for the Death of Sardanapal painting linked to above.
Then, I assure you that you will never have the slightest bit of worry regarding cranking the story and the gameplay together. You will find the story that makes use of the gameplay to convey the message. I personally believe that that is what matters the most. So scoop those gameplay nuggets.
By the way, this is not how Jon Blow thinks we should make games, because this disconnects the message from the gameplay. If, like him, you can create an experience that is contained within the gameplay and have the player extract the message himself from that experience, that's also extremely cool.