Measuring the polarization of a single photon typically results in its destruction. We propose, demonstrate, and completely characterize a quantum nondemolition (QND) scheme for realizing such a measurement nondestructively. This scheme uses only linear optics and photodetection of ancillary modes to induce a strong nonlinearity at the single-photon level, nondeterministically. We vary this QND measurement continuously into the weak regime and use it to perform a nondestructive test of complementarity in quantum mechanics. Our scheme realizes the most advanced general measurement of a qubit to date: it is nondestructive, can be made in any basis, and with arbitrary strength.