Yes, priests can build shrines, but there are limits and there needs to be a certain amount of people.
In city regions, you need what? 10% of the population converted before you can build a shrine? Without a temple you actually will never be able to recruit that many because for some reason there are arbitrary limits on the number of people who can follow your religion without a temple.
Makes no sense.