Churches provide a product, specifically a service which people attend and consume. They often times profit from providing this service. They use the infrastructure of the city in which they operate. Therefore, being part of the community, they should give their fair share since they benefit from the roads, police service, fire service that makes their establishment profitable and possible.
No, churches should not give up their tax exempt status, because they are a valid charity. They should be able to maintain their status, because the ability to have a tax deduction encourages people to give money to the charity. Charities should not have to pay taxes, and a church should not be different just because it is religious.