We present the results of an all-sky radio survey between 5 and 9GHz of sky areas surrounding all unassociated {gamma}-ray objects listed in the Fermi Large Area Telescope Second Source Catalog (2FGL). The goal of these observations is to find all new {gamma}-ray active galactic nucleus (AGN) associations with radio sources >10mJy at 8GHz. We observed with the Very Large Array and the Australia Telescope Compact Array the areas around unassociated sources, providing localizations of weak radio point sources found in 2FGL fields at arcmin scales. Then we followed-up a subset of those with the Very Long Baseline and the Long Baseline Arrays to confirm detections of radio emission on parsec-scales. We quantified association probabilities based on known statistics of source counts and assuming a uniform distribution of background sources. In total we found 865 radio sources at arcsec scales as candidates for association and detected 95 of 170 selected for follow-up observations at milliarcsecond resolution. Based on this we obtained firm associations for 76 previously unknown {gamma}-ray AGNs. Comparison of these new AGN associations with the predictions from using the Wide-field Infrared Survey Explorer color-color diagram shows that half of the associations are missed. We found that 129 out of 588 observed {gamma}-ray sources at arcmin scales not a single radio continuum source was detected above our sensitivity limit within the 3{sigma} {gamma}-ray localization. These "empty" fields were found to be particularly concentrated at low Galactic latitudes. The nature of these Galactic {gamma}-ray emitters is not yet determined.