There are actually some roguelikes that have long successful story paths - they are the type where the deaths don't end the story, but are just a milestone in it. For example, if you had a group of people trying to survive a catastrophe, every time you lost one person you'd just switch to another unless you ran out. The story would be that of the group as a whole surviving the catastrophe, or failing to do so. Also, in some roguelikes 'death' is actually being knocked unconscious outside the tower/dungeon, thus needing to start at floor 1 again. Azure Dreams is an example of this kind - the story takes place mainly in the home base town outside the tower. The only tower story events happen the first time you reach each level (and many levels have none) or the first/only time you acquire a key item.

I think roguelikes in general tend to do a lot with item flavor text. Funny messages for various death types are popular in games like Terraria and would fit in a roguelike too. Messages if a trap goes off in a room, or the first time per life that each monster type appears or an item type appears...

(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?").

I'll consider it, but my gut feeling is no on NPCs, just the extra dev effort required for a very minor part of the game.

Depending on your game, NPCs needn't be terribly complex: at their simplest, they may be little more than re-skinned sign-posts; only slightly more complex might be NPCs with a shop attached, or who change what they say when given a "key" item (which might use logic similar to any locked doors that you might already have in the game).

I did think of the players thoughts... it may be a bit weird and awkward given the first-person perspective ...

I don't think so; it's not at all unknown, even outside of noir detective stories. It's perhaps not ideal, but it's one possible way of handling a story in the absence of other actors.

... and I'm not sure if we have voice talent

I'm honestly not convinced that voice acting is as important as some other seem to consider it to be, but I won't gainsay you on this--you know your project better than I, and if this is an obstacle then fair enough.

I like the idea of the pieces.

(I take it that you mean the suggestion in my responses (2) and (3) above--if not, then ignore! ^^; ) I do think that it fits quite nicely with the random-generation of a roguelike.

Another interesting way to put a bit of story into a horror game is putting graffiti on the walls. Or some kind of poster or poem or advertisement - anything that might logically be in the kind of setting you've got.

It doesn't need to be an in your face conventional story. The story can be told through little clues written on walls, journals of people lying around that all contain a small piece of crucial information, whispers coming from seemingly nowhere, things of that nature. To increase replayability you could make it so that only a small portion of the clues can be found in a single playthrough. Also you could have some scripted events that are going to happen no matter what. Honestly story-telling in video games has only had the surface scratched so far and you can still get highly experimental with it.