Can't you get countable choice with zf? Countable means there is a bijection to the naturals, so you can always pick the element that corresponds with 0.