Live shows are typically actually no more "random" than recordings. Which is to say that touring bands commonly play to click tracks and backing parts that have been pre-recorded and have a specific pre-determined TEMPO. When that's the case, you can simply create a projection effect that brings the words up at the proper place in the score of the song and use a MIDI track to trigger the words.
If the performance is truly free form over time, then you have to find another way to trigger the advance of the visuals to the tempo. Again, it wouldn't be a huge problem depending on the kind of music and whether there's a waveform event like a kick drum or something that determines the tempo of the performance, you could just set a trigger to watch for the pulse of the drum and do the same MIDI trick for a computer's advance of what would amount to a series of graphic slides with the words in order.
If EVERYTHING is free form, and you don't know second to second what's going to happen next - then I'm afraid you have to hire some schlub to sit backstage and LISTEN to the singer and trigger the damn words manually.
Lots of different ways to get from point A to point B with something like this.