Bill,
This is an interesting thread. I would say you would have to do some footwork here & go to each church in question, talk to the Priest, Minister,Pastor, Rabbi, or whoever is in charge first. Also remember that most churches already have a band, singers, or what have you already within their congregation. There could cause a conflict of interests. You could try to find out what programs & groups they have within the congregation to see who is charge of Dinners, Dances, Shows, etc. Then find out if your act would fit in to their curriculum, & what kind of entertainment they are looking for & what they are will to pay within their budget.. I would say it would just take some TLC and a little perseverance and you could be successful.