We present a new first-principle framework for the prediction of effective properties and statistical correlation lengths for multicomponent random media. The methodology is based upon a variational hierarchical decomposition procedure which recasts the original multiscale problem as a sequence of three scale-decoupled subproblems. The focus of the current paper is the computationally intensive mesoscale subproblem, which comprises: Monte-Carlo acceptance-rejection sampling; domain generation and parallel partition based on Voronoi tesselation; parallel Delaunay mesh generation; homogenization-theory formulation of the governing equations; finite-element discretization; parallel iterative solution procedures; and implementation on message passing multicomputers, here the Intel iPSC/860 hypercube. Two (two-dimensional) problems of practical importance are addressed: heat conduction in random fibrous composites, and creeping flow through random fibrous porous media.