We study the homogenization of a $G$-equation which is advected by a divergence free stationary vector field in a general ergodic random environment. We prove that the averaged equation is an anisotropic deterministic G-equation and we give necessary and sufficient conditions in order to have enhancement. Since the problem is not assumed to be coercive it is not possible to have uniform bounds for the solutions. In addition, as we show, the associated minimal (first passage) time function does not satisfy, in general, the uniform integrability condition which is necessary to apply the sub-additive ergodic theorem. We overcome these obstacles by (i) establishing a new reachability (controllability) estimate for the minimal function and (ii) constructing, for each direction and almost surely, a random sequence which has both a long time averaged limit (due to the sub-additive ergodic theorem) and stays (in the same sense) asymptotically close to the minimal time.
