We present two methods for determining the significance of a stochastic gravitational-wave (GW) background affecting a pulsar-timing array, where detection is based on evidence for quadrupolar spatial correlations between pulsars. Rather than constructing noise simulations, we eliminate the GWB spatial correlations in the true data sets to assess detection significance with all real data features intact. In our first method, we perform random phase shifts in the signal-model basis functions. This phase shifting eliminates signal phase coherence between pulsars, while keeping the statistical properties of the pulsar timing residuals intact. We then explore a method to null correlations between pulsars by using a “scrambled” overlap-reduction function in the signal model for the array. This scrambled function is orthogonal to what we expect of a real GW background signal. We demonstrate the efficacy of these methods using Bayesian model selection on a set of simulated data sets that contain a stochastic GW signal, timing noise, undiagnosed glitches, and uncertainties in the Solar system ephemeris. Finally, we introduce an overarching formalism under which these two techniques are naturally linked. These methods are immediately applicable to all current pulsar-timing array data sets, and should become standard tools for future analyses.