Wouldn't the Coupons idea still be linear? Since as I understand it, the coupons unlock a segment of the plot. The player needs to "earn" each advancement, therefore the plot is still linear, just split up.
I've not a chance to play it yet, but what about Zelda Ocarina of Time? As I understand it, Link goes through various stages of his life, kind of like flashbacks. Again, I haven't played it yet, so I'm possibly misunderstanding.
What would REALLY be a nonlinear plot line would be if someone made a game out of Slaughterhouse Five. Completing each successful stage/mission would result in a time warp to some random point in the main character's life (childhood, deathbed, etc).