We propose and demonstrate first steps towards schemes where the librational mode of levitating ferromagnets is strongly coupled to the electronic spin of Nitrogen-Vacancy (NV) centers in diamond. Experimentally, we levitate ferromagnets in a Paul trap and employ magnetic fields to attain oscillation frequencies in the hundreds of kHz range with Q factors close to $10^4$. These librational frequencies largely exceed the decoherence rate of NV centers in typical CVD grown diamonds offering prospects for sideband resolved operation. We also prepare and levitate composite diamond-ferromagnet particles and demonstrate both coherent spin control of the NV centers and read-out of the particle libration using the NV spin. Our results will find applications in ultra-sensitive gyroscopy and bring levitating objects a step closer to spin-mechanical experiments at the quantum level.