After talking about the use of time travel in fiction and games I figured it was time to put up or shut up. So here's how I would make a game with time travel as a narrative and gameplay tool.
First off, the method of time travel I'm thinking of involves having time pass universally no matter what point in time you are. So if you're in time period A, travel to time B and spend the day there, you return to time A one day after you left. Think of the Langoliers...except less goofy.
Regardless of what style of game this is, FPS or RPG or...OMG I guess? Let's say the game has five different time periods that you have to travel to, A through E. Each period has a primary goal that has a direct impact on the others but that impact changes depending on what order you complete the goals. For example, the primary goal of time A results in you killing a criminal. But unless you go to time C first to collect proof that he's a genocidal monster you end up as a wanted felon in time D. However, going to time C first then killing him in time A makes you a hero in time D.
I think that would be more interesting then most other uses of time travel I've seen. Each time you play through the game you have complete freedom over what order you go to each time period and when you accomplish each goal. But since time passes equally in each time period you can't backtrack to undo something. No looping timelines here. But because you have the freedom the game could have as many different combinations of play as there are time periods. Order them A to E or the other way around.
Obviously this could use some more story, characters...plot and etc. But there's the basic idea at least.