One of the main signatures of primordial non-Gaussianity of the local type is a scale-dependent correction to the bias of large-scale structure tracers such as galaxies or clusters, whose amplitude depends on the bias of the tracers itself. The dominant source of noise in the power spectrum of the tracers is caused by sampling variance on large scales (where the non-Gaussian signal is strongest) and shot noise arising from their discrete nature. Recent work has argued that one can avoid sampling variance by comparing multiple tracers of different bias, and suppress shot noise by optimally weighting halos of different mass. Here we combine these ideas and investigate how well the signatures of non-Gaussian fluctuations in the primordial potential can be extracted from the two-point correlations of halos and dark matter. On the basis of large N-body simulations with local non-Gaussian initial conditions and their halo catalogs we perform a Fisher matrix analysis of the two-point statistics. Compared to the standard analysis, optimal weighting and multiple-tracer techniques applied to halos can yield up to 1 order of magnitude improvements in fNL-constraints, even if the underlying dark matter density field is not known. In this case one needs to resolve all halos down to 1010h-1Msun at z=0, while with the dark matter this is already achieved at a mass threshold of 1012h-1Msun. We compare our numerical results to the halo model and find satisfactory agreement. Forecasting the optimal fNL-constraints that can be achieved with our methods when applied to existing and future survey data, we find that a survey of 50h-3Gpc3 volume resolving all halos down to 1011h-1Msun at z=1 will be able to obtain σfNL˜1 (68% cl), a factor of ˜20 improvement over the current limits. Decreasing the minimum mass of resolved halos, increasing the survey volume or obtaining the dark matter maps can further improve these limits, potentially reaching the level of σfNL˜0.1. This precision opens up the possibility to distinguish different types of primordial non-Gaussianity and to probe inflationary physics of the very early Universe.