I am starting to learn about Lebesgue integrals, and my textbook introduces the integral first before moving on to measure.
The proof of the monotone convergence theorem (for $L_{inc}$, the set of $g(x)$ such that for some increasing sequence of step functions, $\phi_k(x)\to g(x)$ almost everywhere) starts by choosing, for each $f_n(x)$, some $\phi_{nk}(x)$. Does this not appeal to some version of the axiom of choice, especially since there are uncountably many choices for $\phi_{nk}$?
If it does, I am eager to learn whether this theorem can be proven without choice, and whether the above approach can be fixed to that end.
I don't see where the axiom of choice would be used.
For step functions you can always choose step functions which obtain rational values and have rational discontinuity points. Since the collection of all such functions is countable, you can fix an enumeration of them, and always choose the least one in the enumeration.
But your question about "uncountably many" is naively understandable, but doesn't make much sense mathematically. You do not need choice to pick one element from an uncountable set; but you do need choice to pick a sequence of elements from a countable set of pairs. Choice is not affected, in general, from how many options you have to choose from, but rather how many choices you need to make.
And while it is true that here you might need infinitely many choices, we can still make them because there is an explicit countable collection which is "sufficiently rich". For the same reason, by the way, many statements in topology that need some form of choice, can still be proved for second countable or separable spaces.