"The well-ordering theorem together with Zorn's lemma are the most important mathematical statements that are equivalent to the axiom of choice"

This is all crazy stuff, but it would be consistent:

No axiom of choice -> no well-ordering -> no smallest number.