Context. The European space astrometry mission Gaia will construct a dense optical QSO-based celestial reference frame. For consistency between optical and radio positions, it will be important to align the Gaia and VLBI frames with the highest possible accuracy. It has been found that only 70 (10%) of the sources from the International Celestial Reference Frame (ICRF) are suitable for establishing this link, either because they are not bright enough at optical wavelengths or because they have significant extended radio emission which precludes reaching the highest astrometric accuracy. Aims: In order to improve the situation, we have initiated a VLBI survey dedicated to finding additional suitable radio sources for aligning the two frames. Methods: The sample consists of 447 optically-bright (magnitude ≤18) extragalactic radio sources, typically 20 times weaker than the ICRF sources, which have been selected by cross-correlating an optical quasar catalog with the NRAO VLA Sky Survey (NVSS). Results: This paper presents the observing strategy to detect, image, and measure accurate radio positions for these sources. It also provides results on the VLBI detectability of the sources, as derived from initial observations with the European VLBI Network in June and October 2007. Based on these observations, a high detection rate of 89% is found, which is promising for the continuation of this project. This high VLBI detection rate for sources from the NVSS catalog is probably due to the selection process, suggesting that optically-bright quasars have compact radio structures. The entire list of radio sources detected (i.e. complete Table 3) is only available in electronic form at the CDS via anonymous ftp to cdsarc.u-strasbg.fr (130.79.128.5) or via http://cdsarc.u-strasbg.fr/viz-bin/qcat?J/A+A/520/A113< Réduire