You will probably have to tell the story piece by piece in small text-dumps. Braid's story was told entirely by reading books (though the gameplay complemented to the overall themes of the game). 1213, a game by Yahtzee, told the story through text logs that you'd come across from time to time. None of these text-dumps were too big, which meant that the player was eager to read them for the story and didn't get bored by them.
I guess that limiting yourself to that kind of storytelling will force you to tell a story which has already happened in the game world (ala System Shock). If you also want to include what is currently happening, you could throw in some cutscene-type moments: overhearing a meeting, listening in on a character talking to himself, and maybe radio messages too, either sent directly to your character (as in BioShock) or intercepted from other sources.
Do you have an idea of what sort of story you'd like to tell?
Secretary of Unknowable Knowledge for the Rock/Dink administration '08