This paper introduces a new program to find high-redshift radio galaxies in the southern hemisphere through ultra-steep spectrum (USS) selection. We define a sample of 234 USS radio sources with spectral indices alpha_408^843 < -1.0 and flux densities S_408 > 200 mJy in a region of 0.35 sr, chosen by cross-correlating the revised 408 MHz Molonglo Reference Catalogue, the 843 MHz Sydney University Molonglo Sky Survey and the 1400 MHz NRAO VLA Sky Survey in the overlap region -40 deg < delta < -30 deg. We present Australia Telescope Compact Array (ATCA) high-resolution 1384 and 2368 MHz radio data for each source, which we use to analyse the morphological, spectral index and polarization properties of our sample. We find that 85 per cent of the sources have observed-frame spectral energy distributions that are straight over the frequency range 408-2368 MHz, and that, on average, sources with smaller angular sizes have slightly steeper spectral indices and lower fractional linear polarization. Fractional polarization is anti-correlated with flux density at both 1400 and 2368 MHz. We also use the ATCA data to determine observed-frame Faraday rotation measures for half of the sample.