We propose an implementation of a universal quantum gate between pairs of spatially separated atoms in a microwave cavity at finite temperature. The gate results from reversible laser excitation of Rydberg states of atoms interacting with each other via exchange of virtual photons through a common cavity mode. Quantum interference of different transition paths between the two-atom ground and double-excited Rydberg states makes both the transition amplitude and resonance largely insensitive to the excitations in the microwave cavity quantum bus which can therefore be in any superposition or mixture of photon number states. Our scheme for attaining ultralong-range interactions and entanglement also applies to mesoscopic atomic ensembles in the Rydberg blockade regime and is scalable to many ensembles trapped within a centimeter sized microwave resonator.