The global average treatment effect (GATE) is a primary quantity of interest in the study of causal inference under network interference. With a correctly specified exposure model of the interference, the Horvitz-Thompson (HT) and Hájek estimators of the GATE are unbiased and consistent, respectively, yet known to exhibit extreme variance under many designs and in many settings of interest. With a fixed clustering of the interference graph, graph cluster randomization (GCR) designs have been shown to greatly reduce variance compared to node-level random assignment, but even so the variance is still often prohibitively large. In this work we propose a randomized version of the GCR design, descriptively named randomized graph cluster randomization (RGCR), which uses a random clustering rather than a single fixed clustering. By considering an ensemble of many different cluster assignments, this design avoids a key problem with GCR where a given node is sometimes "lucky" or "unlucky" in a given clustering. We propose two randomized graph decomposition algorithms for use with RGCR, randomized 3-net and 1-hop-max, adapted from prior work on multiway graph cut problems. When integrating over their own randomness, these algorithms furnish network exposure probabilities that can be estimated efficiently. We develop upper bounds on the variance of the HT estimator of the GATE under assumptions on the metric structure of the interference graph. Where the best known variance upper bound for the HT estimator under a GCR design is exponential in the parameters of the metric structure, we give a comparable variance upper bound under RGCR that is instead polynomial in the same parameters. We provide extensive simulations comparing RGCR and GCR designs, observing substantial reductions in the mean squared error for both HT and Hájek estimators of the GATE in a variety of settings.