You know, Microscope RPG would actually work really well for the "storytelling" mechanics.

I do stuff like this pretty regularly. The closest to actually doing this exact idea is something I'm running right now.

It's an Eclipse Phase game, and in case you don't know, it's a futuristic scifi game that has the ability to transfer your mind in a digital format to another body. You can even make backups of your mind, in case your current one can't be recovered. I started the players off telling them they work doing covert ops, and don't ever get to know the job (they are woken up with a backup from before the job, and given payment). This time, though, they are waking up with what is apparently a very old backup (5 years have gone by that these backups don't have memories of), in cheap bodies, in the middle of no where, with no money, and people are trying to kill them.

They now have to try to find copies of their own minds that actually remember the missions they were on to try to puzzle out what happened. Each time they find one of these backups, I have them actually play out the mission they were on, sort of writing the past as they go.

It's hilarious, and I don't even mind the meta-gaming going on (specifically trying to leave themselves clues from the past, even though their past self wouldn't have known to do that -stuff like that). I've got some next-level mind-fuck shit planned for the finale, and it's going to be amazing.

Yours has the fun part of it being "tall tales", and anything goes, and if there is anything that doesn't quite match up to the truth later, it can be explained away with remembering it wrong or "embellishing" the truth.