We present a source catalogue and first results from a deep, blind radio survey carried out at 20 GHz with the Australia Telescope Compact Array, with follow-up observations at 5.5, 9 and 18 GHz. The Australia Telescope 20 GHz (AT20G) deep pilot survey covers a total area of 5 deg^2 in the Chandra Deep Field South and in Stripe 82 of the Sloan Digital Sky Survey. We estimate the survey to be 90% complete above 2.5 mJy. Of the 85 sources detected, 55% have steep spectra (alpha_{1.4}^{20} < -0.5) and 45% have flat or inverted spectra (alpha_{1.4}^{20} >= -0.5). The steep-spectrum sources tend to have single power-law spectra between 1.4 and 18 GHz, while the spectral indices of the flat- or inverted-spectrum sources tend to steepen with frequency. Among the 18 inverted-spectrum (alpha_{1.4}^{20} >= 0.0) sources, 10 have clearly defined peaks in their spectra with alpha_{1.4}^{5.5} > 0.15 and alpha_{9}^{18} < -0.15. On a 3-yr timescale, at least 10 sources varied by more than 15% at 20 GHz, showing that variability is still common at the low flux densities probed by the AT20G-deep pilot survey. We find a strong and puzzling shift in the typical spectral index of the 15-20 GHz source population when combining data from the AT20G, Ninth Cambridge and Tenth Cambridge surveys: there is a shift towards a steeper-spectrum population when going from ~1 Jy to ~5 mJy, which is followed by a shift back towards a flatter-spectrum population below ~5 mJy. The 5-GHz source-count model by Jackson & Wall (1999), which only includes contributions from FRI and FRII sources, and star-forming galaxies, does not reproduce the observed flattening of the flat-spectrum counts below ~5 mJy. It is therefore possible that another population of sources is contributing to this effect.