The answer to this depends on the logical framework we decide to adopt.
In intuitionist logic this argument is a fallacy. There is no proof by contradiction (PbC) in intuitionist logic (IL). For example, the proof for the existence of infinite numbers would not apply to I.L. Assume there are finite numbers. Then by the principle of good ordering there must be a largest number. Show this largest number and I can show largest + 1. Contradiction met = means the opposite of the premise is true : there are infinite numbers.
This proof only works in classical logic where PbC is an accepted derivation.
Similar argument is popularly used for the existence of God as you yourself have hinted at.
In classic logic you may be able to get away with this argument. God exists because you cannot prove He doesn't exist.
It all depends on the logic rules you set before the argument.