Paolo Aluffi's book "Algebra: Chapter 0" mentions that compactness of first order logic is sufficient to prove this. I don't know the ultrafilter lemma.