(I'm a little tired, so my apologies if I miss anything in the below.)
1) The tools that are available may depend on the specifics of your game. Nothing says that a roguelike can't have NPCs (perhaps hallucinatory, if your setting precludes physical non-monstrous entities other than the player) with whom to converse, or short cutscenes that trigger on certain (randomly-placed) events, for two examples.
Another idea might be to take a leaf from The Binding of Isaac: divide the game into sections, and have cutscenes between them.
Yet another might be to relate the story through the player-character's thoughts at various salient points.
2) As suggested above, one possibility might be to build up the story through randomly-selected events built into your levels.
For example, let's say that your story is told in three rooms/encounters, which we'll call A, B, and C. In the player's first run, the randomly-generated level includes B. In the second, no story elements come up. In the third, A appears. And so on; the player thus pieces together the story over the course of several runs.
3) One thing that comes to mind is to make each piece interesting in and of itself. While the over-arching story might rely on finding most or all of the pieces, have each piece provide some insight or thought on its own.
For example, let's say that your story covers the rule of a tyrant king: how he rose to power, how he established his iron grip, how he ruled, and how he was at last thrown down, with a mystery threaded throughout as to who it was that defeated him. One piece of the story might tell you (slightly more verbosely) that the Tyrant King carried a great mace named "Honn", with which he would never allow himself to be parted (save once: when he was defeated), and which was named for his father. This piece thus, as well as advancing the overall story, (hopefully) provides a bit of characterisation, a few tidbits of information, and hints at further story elements that the player might look for ("was the mace tied to his success?").