Many physical systems, such as natural porous media, are highly heterogeneous and characterized by parameters that are often uncertain due to the lack of sufficient data. This uncertainty (randomness) occurs on a multiplicity of scales. We focus on random composites with the two dominant scales of uncertainty: a large-scale uncertainty in the spatial arrangement of materials and a small-scale uncertainty in the parameters within each material. We propose an approach that combines random domain decompositions (RDD) and polynomial chaos expansions (PCE) to account for the large- and small-scales of uncertainty, respectively. We present a general framework and use one-dimensional diffusion to demonstrate that our combined approach provides robust, non-perturbative approximations for the statistics of the system states.