We present an elemental abundance analysis for four newly discovered ultra metal-poor stars from the Hamburg/ESO survey, with $mathrm{[Fe/H]}leq-4$. Based on high-resolution, high signal-to-noise spectra, we derive abundances for 17 elements in the range from Li to Ba. Three of the four stars exhibit moderate to large over-abundances of carbon, but have no enhancements in their neutron-capture elements. The most metal-poor star in the sample, HE~0233$-$0343 ($mathrm{[Fe/H]} = -4.68$), is a subgiant with a carbon enhancement of $mathrm{[C/Fe]}= +3.5$, slightly above the carbon-enhancement plateau suggested by Spite et al. No carbon is detected in the spectrum of the fourth star, but the quality of its spectrum only allows for the determination of an upper limit on the carbon abundance ratio of $mathrm{[C/Fe]} < +1.7$. We detect lithium in the spectra of two of the carbon-enhanced stars, including HE~0233$-$0343. Both stars with Li detections are Li-depleted, with respect to the Li plateau for metal-poor dwarfs found by Spite & Spite. This suggests that whatever site(s) produced C either do not completely destroy lithium, or that Li has been astrated by early-generation stars and mixed with primordial Li in the gas that formed the stars observed at present. The derived abundances for the $alpha$-elements and iron-peak elements of the four stars are similar to those found in previous large samples of extremely and ultra metal-poor stars. Finally, a large spread is found in the abundances of Sr and Ba for these stars, possibly influenced by enrichment from fast rotating stars in the early universe.