You don't NEED laminate, but why not? Yes, it'll increase install price... but it'll also increase longevity by a lot. This is a church...there will be tons of people, and kids, getting their grimy fingers all over the pretty picture. All it takes is 1 cleaner to use the wrong cleaning solution, and your multi-thousand dollar job just got streaks of ink removed from it. You should always laminate if its intended to be used longer than short term... it's such a small cost in the long run, and will double longevity in most circumstances.
Also, it all depends on the type of paint. Some low voc is ok - most arent. The formula they use for low voc causes many vinyls not to stick... There are some that will though. Talk to your supplier and ask for a sample of a couple different vinyls, stick it to the wall, and come back in 24 hours and try to peel it off. Whichever one is the toughest to peel off, is the one you want.
Do whatever samples in an inconspicuous area though. Fresh paint tends to peel off with the vinyl... Also make them aware of that, if/when they remove the vinyl, it may bring up some of the paint with it. Most of the time it's fine, but depending on how cheap/brand of paint they used, it's a risk.