Sr_{2}CuTeO_{6} is a square-lattice Néel antiferromagnet with superexchange between first-neighbor S=1/2 Cu spins mediated by plaquette centered Te ions. Substituting Te by W, the affected impurity plaquettes have predominantly second-neighbor interactions, thus causing local magnetic frustration. Here we report a study of Sr_{2}CuTe_{1-x}W_{x}O_{6} using neutron diffraction and μSR techniques, showing that the Néel order vanishes already at x=0.025±0.005. We explain this extreme order suppression using a two-dimensional Heisenberg spin model, demonstrating that a W-type impurity induces a deformation of the order parameter that decays with distance as 1/r^{2} at temperature T=0. The associated logarithmic singularity leads to loss of order for any x>0. Order for small x>0 and T>0 is induced by weak interplane couplings. In the nonmagnetic phase of Sr_{2}CuTe_{1-x}W_{x}O_{6}, the μSR relaxation rate exhibits quantum critical scaling with a large dynamic exponent, z≈3, consistent with a random-singlet state.