We propose and demonstrate first steps towards schemes where the librational mode of levitating ferromagnets can be strongly coupled to the electronic spin of Nitrogen-Vacancy (NV) centers in diamond. Experimentally, we levitate soft 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 resolved sideband 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.