We've looked at a number of ways of giving the player the feeling that he or she can create his or her own story. Let's review that list and expand upon it a bit:
Multi-path structure, so that the plot actually splits
Different ways of accomplishing your missions
Choosing different weapons, armor, spells, and so on
Choosing different characters to play, with each role offering it's own abilities and choices of weapons, armor, spells, etc.
Different styles of accomplishing the mission, such as stealth or force
Giving a game with a story some additional non-story ways of playing, such as:
The ability to explore environments (and usually find something of potential use or acquiring skills or ranking that allows you to pursue either story mode or non-story mode activities more effectively)
Mini-games (games within the game), which can be quite creative in nature. GTA III and Vice City allow you to steal police cars and get assignments to track down and kill criminals; you can grab an ambulance and rescue people; you can cause mayhem on foot or in cars in numerous different ways.