I think that the biggest problem with doing any kind of trailer for a game like this is that there aren't a lot of interesting things to show. Don't get me wrong, I love it, but if you have never played any kind of roguelike game you will just look at it and think: What the hell did I just watch?
Another problem is actually trying to use game footage. The game isn't designed to be played like a fast paced action game, nor does it look like one. There aren't any graphics to draw attention away from the gameplay, which is a good thing for the guy playing it, because he can use his imagination to create a whole world in his mind. However, the person watching it will just get confused because the only thing he sees is a B that's throwing things at a @ in a labyrinth filled with . and #.
I think that the best way to actually get any publicity is to post some sessions on youtube or whatever. Post a link to this site in the comment box (Duh =P), try to explain what a roguelike is (Just the basics), so that people who have never played it before know what they are staring at and try to keep it short, use cuts between action sequences so people don't have to watch the boring bits (Or, if you want to post a complete game session, don't) but you already figured that out =P