Localized electronic and nuclear spin qubits in the solid state constitute a promising platform for storage and manipulation of quantum information, even at room temperature. However, the development of scalable systems requires the ability to entangle distant spins, which remains a challenge today. We propose and analyze an efficient, heralded scheme that employs a parity measurement in a decoherence free subspace to enable fast and robust entanglement generation between distant spin qubits mediated by a hot mechanical oscillator. We find that high-fidelity entanglement at cryogenic and even ambient temperatures is feasible with realistic parameters and show that the entangled pair can be subsequently leveraged for deterministic controlled-NOT operations between nuclear spins. Our results open the door for novel quantum processing architectures for a wide variety of solid-state spin qubits.