im thinking off the wall here (especially since its a christian church group - but it may work out great)
graffiti!
yeh i know but hear me out
you pay for the advertising space (i.e a billboard ect)
and then you pay some local kids (if there are any artisitic ones) or an artist
and get them to graffiti that space - with say your web adress or a slogan or such
(get them to do it in the dead of night - and you have gosip) - ps make sure the police are aware
by the way this depends on how much you want to spend
but seems as its local and for the church you may be able to angle - some freebies