We report a nonlinear alignment-to-orientation conversion measurement of atomic spins that simultaneously shows super-Heisenberg scaling and achieves projection-noise limited sensitivity of 990 spins, 20 dB more sensitive than the previous best nonlinear measurement. Using this technique, we have recently demonstrated conditional spin squeezing of the atomic ensemble, and entanglement-enhanced measurement sensitivity useful for optical magnetometry. In addition, we use a novel technique to explicitly certify that the measurement fulfills all the conditions required for quantum non-demolition measurement.