The non-equilibrium dynamics of a gas of cold atoms in which Rydberg states are off-resonantly excited is studied in the presence of noise. The interplay between interaction and off-resonant excitation leads to an initial dynamics where aggregates of excited Rydberg atoms slowly nucleate and grow, eventually reaching long-lived meta-stable arrangements which then relax further on much longer timescales. This growth dynamics is governed by an effective Master equation which permits a transparent and largely analytical understanding of the underlying physics. By means of extensive numerical simulations we study the many-body dynamics and the correlations of the resulting non-equilibrium states in various dimensions. Our results provide insight into the dynamical richness of strongly interacting Rydberg gases in noisy environments, and highlight the usefulness of these kind of systems for the exploration of soft-matter-type collective behaviour.