We develop a time domain random walk approach for conservative solute transport in heterogeneous media where medium properties vary over a distribution of length scales. The spatial transition lengths are equal to the heterogeneity length scales, and thus determined by medium geometry. We derive analytical expressions for the associated transition times and probabilities in one spatial dimension. This approach determines the coarse-grained solute concentration at the interfaces between regions; we derive a generalized master equation for the evolution of the coarse-grained concentration and reconstruct the fine-scale concentration using the propagator of the subscale transport mechanism. The performance of this approach is demonstrated for diffusion under random retardation in power-law media characterized by heavy-tailed lengthscale and retardation distributions. The coarse representation preserves the correct late-time scaling of concentration variance, and the reconstructed fine-scale concentration is essentially identical to that obtained by direct numerical simulation by random walk particle tracking.