We report on studies of the viability and sensitivity of the Askaryan Radio Array (ARA), a new initiative to develop a Teraton-scale ultra-high energy neutrino detector in deep, radio-transparent ice near Amundsen-Scott station at the South Pole. An initial prototype ARA detector system was installed in January 2011, and has been operating continuously since then. We report on studies of the background radio noise levels, the radio clarity of the ice, and the estimated sensitivity of the planned ARA array given these results, based on the first five months of operation. Anthropogenic radio interference in the vicinity of the South Pole currently leads to a few-percent loss of data, but no overall effect on the background noise levels, which are dominated by the thermal noise floor of the cold polar ice, and galactic noise at lower frequencies. We have also successfully detected signals originating from a 2.5 km deep impulse generator at a distance of over 3 km from our prototype detector, confirming prior estimates of kilometer-scale attenuation lengths for cold polar ice. These are also the first such measurements for propagation over such large slant distances in ice. Based on these data, ARA-37, the 200 km^2 array now under construction, will achieve the highest sensitivity of any planned or existing neutrino detector in the 10^{16}-10^{19} eV energy range.