We study the spatial and orientational distribution of rodlike counterions (such as mobile nanorods) as well as the effective interaction mediated by them between two plane-parallel surfaces that carry fixed (quenched) heterogeneous charge distributions. The rodlike counterions are assumed to have an internal charge distribution, specified by a multivalent monopolar moment and a finite quadrupolar moment, and the quenched surface charge is assumed to be randomly distributed with equal mean and variance on the two surfaces. While equally charged surfaces are known to repel within the traditional mean-field theories, the presence of multivalent counterions has been shown to cause attractive interactions between uniformly charged surfaces due to the prevalence of strong electrostatic couplings that grow rapidly with the counterion valency. We show that the combined effects due to electrostatic correlations (caused by the coupling between the mean surface field and the multivalent, monopolar, charge valency of counterions) as well as the disorder-induced interactions (caused by the coupling between the surface disorder field and the quadrupolar moment of counterions) lead to much stronger attractive interactions between two randomly charged surfaces. The interaction profile turns out to be a nonmonotonic function of the intersurface separation, displaying an attractive minimum at relatively small separations, where the ensuing attraction can exceed the maximum strong-coupling attraction (produced by multivalent monopolar counterions between uniformly charged surfaces) by more than an order of magnitude.