In the local universe, galaxies in clusters show different properties compared to more isolated systems. Understanding how this difference originates and whether it is already in place at high redshift is still a matter of debate. Thanks to uniquely deep optical spectra from the VANDELS survey, we investigate environmental effects on the stellar mass-metallicity relation (MZR) for a sample of ~1000 star-forming galaxies at 2<z<4. We complement our dataset with MOSFIRE follow-up of 21 galaxies to study the environmental dependence of the gas-phase MZR. Robust stellar and gas metallicities are derived, respectively, from well-calibrated photospheric absorptions features at 1501 and 1719 Åin the stacked spectra, and from optical emission lines ([OII]3726-3729, [OIII]5007, and Hbeta) in individual systems. We characterize the environment through multiple criteria by using the local galaxy density maps previously derived in VANDELS. We find that environmental effects are weak at these redshifts, and more important around the densest overdensity structures, where galaxies have a lower stellar Z (by 0.2 dex) and a lower gas-phase Z (by 0.1 dex) compared to the field, with a significance of 1 and 2 sigma, respectively. Crucially, this offset cannot be explained by a selection effect due to a higher SFR, a fainter UV continuum, or different dust attenuations and stellar ages. Despite the still low S/N of our results, we propose a combination of increased mergers and high-speed encounters, more efficient AGN feedback in dense cores, and cold gas inflows as viable mechanisms diluting the metal content of overdense galaxies or expelling their metals to the IGM. Finally, some tensions remain with semi-analytic models and hydrodynamical simulations, which predict no significant offset as a function of host halo mass, suggesting that an explicit implementation of environmental processes is needed.