To add to the answer about what is the weakest choice-like principle required: let me take this opportunity to mention Consequnces of the Axiom of Choice by Rubin and Howard. This is form 93 in the book and no known exact equivalents are listed for it. An extensive implication table is available.

For instance, as pointed out, the existence of a non-trivial ultrafilter on $\omega$ is sufficient, and BPI (the boolean prime ideal theorem) implies the existence of such an ultrafilter. According to the book, neither of these implications is reversible.

Another intermediate principle the book mentions is the sock selection principle (every family of pairs has a choice function). This is implied by BPI and implies the existence of a non-measurable set, and neither of these is reversible.

To add to the answer about what is the weakest choice-like principle required: let me take this opportunity to mention Consequences of the Axiom of Choice by Rubin and Howard. This is form 93 in the book and no known exact equivalents are listed for it. An extensive implication table is available.

For instance, as pointed out, the existence of a non-trivial ultrafilter on $\omega$ is sufficient, and BPI (the boolean prime ideal theorem) implies the existence of such an ultrafilter. According to the book, neither of these implications is reversible.

Another intermediate principle the book mentions is the sock selection principle (every family of pairs has a choice function). This is implied by BPI and implies the existence of a non-measurable set, and neither of these is reversible.