I've done this a couple of times and it is difficult. Your stuck to your pre-programmed sequence, and so the worship leader needs to follow your program exactly. I usually start at least 2 weeks back - get the worship leader to tell me exactly how many repeats/choruses etc. Then get the recorded thing to him/her to listen and to get changes done. Everybody, including all backup singers, need to be very familiar with the the sequences. One mistake in timing by one person and you're in trouble.
If this is the case, any sequencing software will do. I use Logic.
But I'm think Ableton live will give more flexibility in this kind of scenerio when you can do many things real time and on the spot including repeating of choruses etc. I've not tried it though.