ApJ in press Preprint typeset using LATEX style emulateapj v. 5/2/11 THE OPTICALLY UNBIASED GRB HOST (TOUGH) SURVEY.

ApJ in press We present simultaneous optical and near-infrared (NIR) spectroscopy of 19 Swift GRB host galaxies with VLT/X-shooter with the aim of measuring their redshifts. Galaxies were selected from The Optically Unbiased GRB Host (TOUGH) survey (15 of the 19 galaxies) or because they hosted GRBs without a bright optical afterglow. Here, we provide emission-line redshifts for 13 of the observed galaxies with brightnesses between F606W> 27 mag and R = 22.9 mag (median R ̃ = 24.6 mag). The median redshift is z ̃ = 2.1 for all, and z ̃ = 2.3 for the TOUGH hosts. Our new data significantly improve the redshift completeness of the TOUGH survey, which now stands at 77 % (53 out of 69 GRBs). They furthermore provide accurate redshifts for nine prototype-dark GRBs (e.g., GRB 071021 at z = 2.452 and GRB 080207 at z = 2.086), which are exemplary of GRBs where redshifts are challenging to obtain via afterglow spectroscopy. This establishes X-shooter spectroscopy as an efficient tool for redshift determination of faint, star-forming, high-redshift galaxies such as GRB hosts. It is hence a further step towards removing the bias in GRB samples that is caused by optically-dark events, and provides the basis for a better understanding of the conditions in which GRBs form. The distribution of column densities as measured from X-ray data (NH,X), for example, is closely related to the darkness of the afterglow and skewed towards low NH,X values in samples that are dominated by bursts with bright optical afterglows