We show that a single photon propagating through a Rydberg-dressed atomic ensemble can exchange its spin state with a single atom. Such a spin-exchange collision exhibits both dissipative and coherent features, depending on the interaction strength. For strong interaction, the collision dissipatively drives the system into an entangled dark state of the photon with an atom. In the weak interaction regime, the scattering coherently flips the spin of a single photon in the multiphoton input pulse, demonstrating a generic single-photon subtracting process. An analytical treatment of this process reveals a universal trade-off between efficiency and purity of the extracted photon, which applies to a wide class of single-photon subtractors. We show that such a trade-off can be optimized by adjusting the scattering rate under a novel phase-matching condition.