The standard LambdaCDM model based on General Relativity (GR) including cold dark matter (CDM) is very successful at fitting cosmological observations, but recent non-detections of candidate dark matter (DM) particles mean that various modified-gravity theories remain of significant interest. The latter generally involve modifications to GR below a critical acceleration scale $sim 10^{-10} , m , s^{-2}$. Wide-binary (WB) star systems with separations $> 5 , kAU$ provide an interesting test for modified gravity, due to being in or near the low-acceleration regime and presumably containing negligible DM. Here, we explore the prospects for new observations pending from the GAIA spacecraft to provide tests of GR against MOND or TeVes-like theories in a regime only partially explored to date. In particular, we find that a histogram of (3D) binary relative velocities against circular velocity predicted from the (2D) projected separations predicts a rather sharp feature in this distribution for standard gravity, with an 80th (90th) percentile value close to 1.025 (1.14) with rather weak dependence on the eccentricity distribution. However, MOND/TeVeS theories produce a shifted distribution, with a significant increase in these upper percentiles. In MOND-like theories {em without} an external field effect, there are large shifts of order unity. With the external field effect included, the shifts are considerably reduced to $sim 0.04 - 0.08$, but are still potentially detectable statistically given reasonably large samples and good control of contaminants. In principle, followup of GAIA-selected wide binaries with ground-based radial velocities accurate to < 0.03 km/s should be able to produce an interesting new constraint on modified-gravity theories.