This phrase has been on the edge of the Dutch Guilder since 1816. Aside from religious reasons, a practical reason it was added was to prevent forgery and clipping.
When the Euro came 'round many people thought it might be appropriate to use a more secular phrase, and many op-eds and arguments were written. But especially the SGP was fiercely against this and enthusiastically campaigned to keep it.
The SGP is a fundamentalist Protestant party. They want to establish a theocracy and outlaw "false" religions. Not paraphrasing here; this is literally in their party program (in this answer I went in to some depth as to why they're still a part of modern Dutch politics).
There was no vote for the design, the minister of finance (Gerrit Zalm) chose it. Why exactly did he choose it? I can't find any clear statements from him about this. Some plausible reasons:
Dutch politics are very much based compromise and consensus. There's even a word for it: polderen. Zalm may have simply not wanted to "ruffle any feathers" to maintain a good working relationship with the SGP (and in significantly lesser degree some other parties, such as the Christian-Democrats). This would benefit his own party in the long run in a quid pro quo fashion.
Similarly, removing it might alienate some religious voters, while keeping the phrase was a lot less likely to alienate more secular minded voters.
Tradition may have played a role. The phrase is from Romans 8:31, and the full Latin phrase Si Deus nobiscum quis contra nos first appeared on coins in the Dutch Republic of 1581 which laid the foundation of the modern Netherlands (thank you MSalters for pointing this out).
To explain the mindset perhaps another example of polderen might help, for example how the Netherlands dealt with the matter of conciousness objections of civil servants against marrying same-sex couples.
Last year in the U.S. Kim Davis stirred up a lot of trouble about this – it was an affair full of conflict, court orders, protests, and all sorts of consternation.
In the Netherlands – where same-sex marriage has been legal since 2001 – we've also had to deal with this situation. But the political approach to it has been very different. Sure, there have been heated and passionate debates – as there should be – but in the end a compromise was reached where civil servants hired before the compromise took effect were allowed to refuse to marry same-sex couples (municipalities still have the obligation to guarantee that same-sex marriages can actually marry though).
