[Pocus]

I suppose that building a temple is not only building the masonry of it. It is also how to create and organize the clergy which comes with. This is why you need a priest, and not just Joe the commander.

And Gods dont worships themselves (and dont even exists - in dominions anyway - if nobody believe in them). So they wont create a temple for themselves too.

But as others said, there is several solution even if you had no initial priest available.