Recent work has emphasized the possibility to probe non-Gaussianity of local type by measuring the power spectrum of highly biased tracers of large scale structure on very large scales. This method is limited by the cosmic variance, by the finite number of structures on the largest scales, and by the partial degeneracy with other cosmological parameters that can mimic the same effect. We propose an alternative method based on the fact that on large scales, halos are linearly biased, but not stochastic, tracers of dark matter: by correlating a highly biased tracer of large scale structure against an unbiased tracer, one eliminates the cosmic variance error, which can lead to a significant increase in signal to noise. For an ideal survey out to z approximately 2, the error reduction can be as large as a factor of 7, which should guarantee a detection of non-Gaussianity from an all-sky survey of this type.