So far as I can tell, there was no debate about the validity of these methods before Brouwer. I rely on Colin McLarty's review of the key example in his 2007 paper "Theology and its discontents: David Hilbert's foundation myth for modern mathematics."
The famous examples from before Hilbert, e.g. Archimedes's method of exhaustion, Euclid's proof that "prime numbers are more than any assigned multitude" is constructive, and Cantor-style diagonal proofs of the existence of transcendental numbers, all are or can easily be made constructive.
By contrast, Hilbert's 1888 proof of the existence of a finite system of invariants was not constructive. But apparently no one objected to it for that reason before Brouwer; Paul Gordan called the proof theological but even he did not reject it.
The starting point for the use of that word is Hilbert's reminiscence of 1923, as quoted and translated by McLarty (p. 13):
Gordan had a certain unclear feeling of the transfinite methods in my first invariant proof, which he expresed by calling the proof "theological".
This was about an unclarity in exposition, bad enough that the editors of the Mathematische Annalen noted that the theorem was not true as stated there. The quote "this is not Mathematics; it is Theology!" appears apocryphal; it's first attribution to Gordan was in an article by Felix Klein in 1928.
The actual attitudes of mathematicians to this proof were, as McLarty says, "practical", e.g. John Grace and Alfred Young in 1903: the method "gives practially no information as to the actual determination of the finite system whose existence it establishes". Turning that from an observation to an objection seems to have started with Brouwer.