You are right, you need to create a new song. Stage Traxx does not have the possibility to have 2 versions of lyrics associated with a song.
I am also in the situation that I gig with two different setups that require different patch changes. I just add both patch changes to my songs and make sure that the midi channels of my devices don't overlap. That way the patch changes that don't belong to the currently connected devices are simply ignored.