Using the linear theory of perturbations in General Relativity, we express a set of consistency relations that can be observationally tested with current and future large scale structure surveys. We then outline a stringent model-independent program to test gravity on cosmological scales. We illustrate the feasibility of such a program by jointly using several observables like peculiar velocities, galaxy clustering and weak gravitational lensing. After addressing possible observational or astrophysical caveats like galaxy bias and redshift uncertainties, we forecast in particular how well one can predict the lensing signal from a cosmic shear survey using an over-lapping galaxy survey. We finally discuss the specific physics probed this way and illustrate how $f(R)$ gravity models would fail such a test.