[I have no idea if/how this would work (open to comments and critique) but I think I'm going to implement it in my current game.]
Reading through the Thousand and One Nights and other old Arabic weirdness to purge my fantasy grammar of some of its lazier pseudo-european tropes got me thinking:
The structure and world of the 1001 Nights is one wherein stories serve as a didactic medium, but also almost as currency, as a medium of exchange and as tools. The framing narrative is one of Scheherazade stringing together story after story to save her own life and that of other potential brides-to-be after her. Within her tellings, characters at risk of death will tell a story as a parable to warn their would-be killers from their intended actions, travelers will tell stories in exchange for room and board.
If story functions as a mechanic here, and a good story can change one's fate, improve one's lot or turn the tables on a situation gone wrong (likewise a bad story or one whose meaning is adversely interpreted often leads to bad ends), why can't we make this a game mechanic?
Start your campaign off like Scheherazade's framing narrative: "Here is a tale of adventure" wherein PCs are doing whatever they're doing (sure, let it even be about the heroes who entered the dungeon and slew the dragon - that doesn't matter at all).
The first time the party comes to an impasse with a monster (even the usually unintelligent monsters should be suddenly sapient when the possibility of a good story is at hand) or an NPC, or in any situation of interaction they wish to get something more (free room and board in a storm), avoid a bad outcome (tax collectors taking their last silver) they say "You would do to me as the hyena-men sought to do to Prince Sameh" or "This reminds me of the story of the falconers"
At this point, you break and take an Inception -esque dive a layer deeper into the narrative. Roll up new characters (Hyena men or Prince Sameh and Retinue, depending on preference in the above example) and play out the one-shot, mini-sandbox or full-fledged-campaign of interactions/combats/intrigue at this narrative level until it seems some arc has played out. Depending on how this concludes (do the Hyena men kill the xenophobic Prince Sameh, or does Sameh play off the hyenas' hubris and outwit them) changes the "moral" of the story; this in turn will impact the events in the higher-order narrative.
PCs will be driven to create a good story, but also one which would have a moral or ending that would grant them a suitable resolution in the higher-order narrative. They finish their story, and the listener, pleased or persuaded by its outcome or moral, resolves the situation to the Party's favor.
If the PCs are in a lower-order narrative and find themselves in a dilemma, they can again interject with the offer of a story to help themselves. One story deeper, now, not a problem.
If there's a TPK or a similarly horrible outcome for the PCs, they find that (barring some real rhetorical flourish) they've probably just told a tale that will seal their death warrant or make them an enemy in the higher-order world.
There is no limit to how deep one goes into the narrative structure, nor any obligation to how far one comes back up. Recalling consistent details by the time one makes it back to a higher-order story is probably difficult, and probably not entirely necessary. The 1001 Nights and similar collections of stories often contain unfinished tales, loose ends and even, to quote the preface of a new translation, a bit of "narrative incompetence". The important thing is that all of the crazy stories you tell about your games are now stories within your games.