Consider the following partition of $\mathbb{Q}^2$ into disjoint classes : $(p_1, p_2) \sim (q_1,q_2)$ if and only if both $p_1 - q_1$ and $p_2 - q_2$ have odds denominators when written in their lowest terms.
Suppose I endow the equivalence class containing $(0,0)$ with some structure (say, a graph structure and a coloring of edges) and suppose I want to transfer this structure to all the other equivalence classes by translation. Do I need some weaker form of choice (like $\textsf{AC}_\omega$ for instance) to do this ?
No. Since $\Bbb Q$ is provable countable, then $\Bbb Q^2$ is provable countable. Therefore we can define all the choice functions we need here, by fixing an enumeration of $\Bbb Q^2$ and considering the least element in the enumeration satisfying whatever we wanted.
(The same argument holds for any countable set. Note, however, that if your set does not have any definition which is provably countable, then it is going to be hard to define such an equivalence relation on your set.)