Does k(X) have a k-basis for every set X, without AC? This question is inspired by Pace Nielsen's recent question Does a left basis imply a right basis, without AC?.
For any field $k$, the field $k(x)$ of rational functions in one variable has an explicit $k$-basis given by partial fractions: the set 
$$B(x,k)=\left\{x^i:i\geq 0\right\}\cup \left\{\frac{x^i}{m(x)^j}:\mbox{$m(x)$ monic irreducible, } 0<j, 0\leq i<\operatorname{deg}(m)\right\}$$
is a basis.
By induction, $k(x_1,\dots,x_n)$ has a $k$-basis  for any $n$, without needing to assume the axiom of choice. The obvious way of doing this gives a basis that depends on the choice of an order for the variables.

In ZF set theory without choice, must $k(X)$ have a $k$-basis for an arbitrary set $X$?

The existence of such a basis certainly doesn't need the full strength of AC. The statement that every set has a total order is known to be independent of ZF but not to imply AC (see for example the various references in Are all sets totally ordered ?). If $X$ has a total order, and for $y\in X$ we let $$X_{<y}=\left\{x\in X: x<y\right\},$$
then the set of finite products $t_1t_2\dots t_n$, where 
$$1\neq t_i\in B\left(y_i,k(X_{<y_i})\right)$$
for some $y_1<\dots < y_n$,
is a $k$-basis of $k(X)$.
 A: If $k= \mathbb{F}_2$, I will show that this implies the axiom of choice for pairs. Suppose $k(X)$ has a basis and let $f$ be a basis element. For any $x$ and $y$ in $X$, let $c(x,y)$ be the coefficient of $f$ in $\frac{x}{x+y} f$. Since $\frac{x}{x+y} f + \frac{y}{x+y} f = f$, we have $c(x,y)+c(y,x)=1$, so one of $c(x,y)$ and $c(y,x)$ is $0$ and the other is $1$; this gives a choice function $X^2 \to X$. 
On the other hand, I believe I can show $k(X)$ has a basis without choice whenever $k$ has characteristic zero. It's a long one -- I'll try to write it up later tonight.
A: As a generalization of David Speyer's argument, here is a proof that if $k(X)$ always has a basis, then the axiom of choice for finite sets of bounded cardinality holds.  In fact, to get the axiom of choice for sets of size at most $n$, we will only use the existence of a nontrivial linear map $\mathbb{F}_p(X)\to \mathbb{F}_p$ for each prime $p\leq n$.
Fix $n$, let $X$ be any set, and suppose there exists a nontrivial linear map $\mathbb{F}_p(X)\to \mathbb{F}_p$ for all $p\leq n$.  Then I claim there is a function that takes any subset $X$ of cardinality between $2$ and $n$ and gives a nonempty proper subset.  By iterating this function until we reach a singleton, we get a choice function for subsets of $X$ of size at most $n$.
For each $p\leq n$, fix a nontrivial linear map $T_p:\mathbb{F}_p(X)\to\mathbb{F}_p$ and an element $f_p\in \mathbb{F}_p(X)$ that is not in the kernel of $T_p$.  Let $S\subseteq X$ be a subset with $2\leq|S|\leq n$ and let $p$ be the least prime dividing $|S|$.  Define a function $g:S\to \mathbb{F}_p$ by $$g(s)=T_p\left(\frac{s}{\sum_{t\in S}t}f_p\right).$$  By linearity of $T_p$, $\sum_s g(s)=T_p(f_p)\neq 0$.  In particular, since $p$ divides $|S|$, the $g(s)$ cannot all be the same.  Let $C(S)=g^{-1}(\{k\})$ for the least $k\geq 0$ for which this set is nonempty.  Then $C(S)$ is a nonempty proper subset of $S$, and $S\mapsto C(S)$ is the desired function.
A: While the question is still unanswered, let me make a couple of observations, showing that the problem is essentially equivalent to construction of symmetric bases (this is already alluded to in Is there a symmetric basis for $\mathbf{Q}(x,y)$? , however we really need infinitely many variables).
Any permutation $\pi$ of $X$ extends uniquely to a $k$-automorphism of $k(X)$, which I will also denote $\pi$. Let me say that a basis $B$ of $k(X)$ is symmetric if $\pi(B)=B$ for every permutation $\pi$, and almost symmetric if there is a finite set $X_0\subseteq X$ such that $\pi(B)=B$ for every permutation $\pi$ fixing $X_0$ pointwise.

Proposition 1: ZF proves that if $k(\{x_n:n\in\mathbb N\})$ has an almost symmetric basis, then $k(X)$ has a basis for every set of variables $X$.

Proof: Pick a basis $B$ of $k(\{y_n:n\in\mathbb N\})$ invariant under all permutations fixing $Y_0=\{y_1,\dots,y_m\}$. If $X$ is finite, $k(X)$ has a basis by induction on $|X|$, for example the one in the question, hence we can assume $X$ is infinite. Fix distinct elements $x_1,\dots,x_m\in X$, and put
$$B_X=\{f(x_1,\dots,x_n):n\ge m,f(y_1,\dots,y_n)\in B,x_{m+1},\dots,x_n\in X\}$$
where the $x_{m+1},\dots,x_n$ are pairwise distinct and disjoint from $\{x_1,\dots,x_m\}$ (this did not fit into the displayed line).
Since any element of $k(X)$ is contained in $k(x_1,\dots,x_n)$ for some $x_1,\dots,x_n$ as above, $B_X$ generates $k(X)$. On the other hand, any finite subset $B_0\subseteq B'$ is also included in some $k(x_1,\dots,x_n)$, and then the symmetry of $B$ implies that $\{f(y_1,\dots,y_n):f(x_1,\dots,x_n)\in B_0\}\subseteq B$, hence it is linearly independent.

Proposition 2: Conversely, if ZF proves that every $k(X)$ has a basis, then ZF(C?) proves that $k(\{x_n:n\in\mathbb N\})$ has an almost symmetric basis.

Proof: Assume (in a model of ZF) that $k(\{x_n:n\in\mathbb N\})$ has no almost symmetric basis, we will extend the universe into a permutation model of ZFA where some $k(X)$ has no basis. This can be made into a model of ZF by the Jech–Sochor embedding theorem; however, I suspect that the forcing involved in that step may need some choice in the ground model, which is why I put the half-hearted C in the statement.
As for the permutation model: we extend the universe with a countable set of atoms $A=\{a_n:n\in\mathbb N\}$. We take the group of all permutations of $A$, and the normal filter generated by stabilizers of finite subsets of $A$. In the resulting permutation model, $k(A)$ has no basis $B$: otherwise $B$ would also be a basis of $k(A)\simeq k(\{x_n:n\in\mathbb N\})$ in the ground model, and it would have finite support, which is exactly what I called almost symmetric above.

Proposition 3: ZF proves that $k(x_1,\dots,x_n)$ has an explicitly definable symmetric basis for every field $k$ and $n\in\mathbb N$.

Proof: Let $B_0$ be any basis of $k(y_1,\dots,y_n)$, which exists by induction on $n$ (e.g., we can take the one described in the question). Let $s_k(x_1,\dots,x_n)$ denote the $k$th elementary symmetric polynomial, and put
$$K=k(s_1(x_1,\dots,x_n),\dots,s_n(x_1,\dots,x_n))\subseteq k(x_1,\dots,x_n).$$
Since the $s_k(\vec x)$ are algebraically independent, $K$ is isomorphic to $k(y_1,\dots,y_n)$, and
$$B_1=\{f(s_1(x_1,\dots,x_n),\dots,s_n(x_1,\dots,x_n)):f(y_1,\dots,y_n)\in B_0\}$$
is a basis of $K$ over $k$. The field $L=k(x_1,\dots,x_n)$ is the splitting field of the degree $n$ polynomial
$$h(x)=(x-x_1)\cdots(x-x_n)$$
over $K$, hence $[L:K]\le n!$. (Actually, it is easy to see that $\mathrm{Gal}(L/K)=S_n$, hence the degree is exactly $n!$.)
I claim that
$$B_2=\{x_1^{\pi(1)}\cdots x_n^{\pi(n)}:\pi\in S_n\}$$
is a $K$-basis of $L$, hence $B=B_1B_2$ is a $k$-basis of $L$, and it is obviously symmetric.
Since we already know $|B_2|\ge[L:K]$, it suffices to show that $B_2$ is $K$-linearly independent. I have no high-level argument for that, but one can prove it by induction on $n$. It will be more convenient to label the variables as $x_0,\dots,x_{n-1}$, and consider $S_n$ as permutations on $\{0,\dots,n-1\}$.
The case $n=1$ is trivial, so assume the statement holds for $n$, we will show it for $n+1$. Aiming for contradiction, let
$$\sum_{\pi\in S_{n+1}}f_\pi(x_0,\dots,x_n)\prod_{i=0}^nx_i^{\pi(i)}=0,\tag{$*$}$$
where the $f_\pi\in K$ are not all zero. We may assume without loss of generality that the rational functions $f_\pi$ are in fact polynomials, and that $x_0\cdots x_n$ does not divide all $f_\pi$.
Let $i_0\le n$. If we substitute $0$ for $x_{i_0}$ in $(*)$, and rename $x_{i_0+1},\dots,x_n$ to $x_{i_0},\dots,x_{n-1}$, we get
$$x_0\cdots x_{n-1}\sum_{\pi'\in S_n}f_{\pi}(x_0,\dots,x_{i_0-1},0,x_{i_0},\dots,x_{n-1})\prod_{i=0}^{n-1}x_i^{\pi'(i)}=0,$$
where
$$\pi(i)=\begin{cases}
\pi'(i)+1&i<i_0,\\
0&i=i_0,\\
\pi'(i-1)+1&i>i_0.
\end{cases}$$
By the induction hypothesis, we obtain that $f_\pi(x_0,\dots,x_{i_0-1},0,x_{i_0+1},\dots,x_n)=0$ whenever $\pi(i_0)=0$. Thus, any $f_\pi$ is divisible by $x_{\pi^{-1}(0)}$, and as it is symmetric, by $x_0\cdots x_n$. This contradicts one of our assumptions.
A: I will show that, if $k$ is countable and has characteristic $0$, then $k(X)$ has a basis. (This whole proof takes place without choice.)
For any $x \in X$, and any $f \in X$, we define an element $r_x(f)$ of $k(X \setminus \{ x \})$ as follows: We have $k(X) \cong k(X \setminus \{ x \})(x)$, which embeds into the field of formal Laurent series $k(X \setminus \{ x \})((x))$. Let $r_x(f)$ be the coefficient of $x^0$ in this Laurent series. For a finite subset $I$ of $X$, let $r(I)$ be
$$\{ f \in k(I) : r_x(f) =0\ \forall_{x \in I} \}.$$
For any finite set $I$, we have $k(I) = \bigoplus_{J \subseteq I} r(J)$ so, since $k(X)$ is the union of the $k(I)$ for $I$ finite, we have $k(X) = \bigoplus_{I \subseteq X,\ \# I < \infty} r(I)$. So it is enough to show $\bigoplus_{I \subseteq X,\ \# I < \infty} r(I)$ has a basis. For this purpose, it is enough to show that $r(\{ x_1, x_2, \ldots, x_n \})$ has an $S_n$ invariant basis. One can then transport this basis to each of the $r(I)$ with $\#I = n$. (More precisely, look at all $n!$ bijections between $\{ 1, \ldots, n \}$; each of them gives a transported basis in $r(I)$. Using the $S_n$ invariance, their union is also a basis in $r(I)$. Thus, we get a basis in $r(I)$ without having to choose an ordering of $I$.)
We fix particular representatives $Sp_{\lambda}$ for the irreducible representations of $S_n$. This can be done in a choice free way by, for example, writing down formulas with Young tableaux. For any $S_n$-representation $W$, let $W_{\lambda} = \mathrm{Hom}_{S_n}(Sp_{\lambda}, W)$. Then there is an obvious map $\bigoplus_{|\lambda| = n} W_{\lambda} \otimes Sp_{\lambda} \longrightarrow W$ and representation theory tells us this map is an isomorphism.
We will show that $r(\{ x_1, \ldots, x_n \})_{\lambda}$ has a countably infinite basis for each $\lambda$, and we will pick a particular one without choice. Thus 
$$r(\{x_1, \ldots, x_n \}) \cong \bigoplus_{|\lambda| = n} k^{\oplus \omega} \otimes Sp_{\lambda} \cong (k S_n)^{\bigoplus \omega}$$
 as $S_n$ representations, and the latter has an obvious permutation basis.
Lemma: Any subspace $V$ of $k^{\oplus \omega}$ has a countable or finite basis, which can be found with no choices.
Proof: Let $e_i$ be the standard basis vectors of $k^{\oplus \omega}$. Let $k^n$ be the subspace of $k^{\oplus \omega}$ spanned by $e_1$, $\dots$, $e_n$. Let $S \subseteq \omega$ be the set of $n$ for which $V \cap k^n \neq V \cap k^{n-1}$. For each $s \in S$, there is a unique $v_s \in V$ such that $v_s \in k^n \cap V$, the coefficient of $e_s$ in $v_s$ is $1$, and $v_s$ does not contain the basis vectors $e_{s'}$ for $s' \in S$, $s < n$. These $v_s$ form a basis.  (In other words, we use row reduced echelon form.) $\square$
Now, $k(x_1, \ldots, x_n)$ has a countable basis. So $r(\{ x_1, \ldots, x_n \})$ has a countable or finite basis by the lemma. The Specht module $Sp_{\lambda}$ has an explicit finite basis which can be written down using standard Young tableaux, so $\mathrm{Hom}(Sp_{\lambda}, r(\{ x_1, \ldots, x_n \}))$ has a basis (note that this is $\mathrm{Hom}$ of vector spaces). The $S_n$ equivariant maps are a subspace of this so, using the lemma again, $\mathrm{Hom}_{S_n}(Sp_{\lambda}, r(\{ x_1, \ldots, x_n \}))$ has an explicit finite or countable basis, as desired.
Finally, we must check that $\mathrm{Hom}_{S_n}(Sp_{\lambda}, r(\{ x_1, \ldots, x_n \}))$ is infinite dimensional. The easiest way is probably to note that, for any distinct positive integers $(a_1, \ldots, a_n)$, the span of $x_1^{a_{\sigma(1)}} \cdots x_n^{a_{\sigma(n)}}$ forms a copy of $k S_n$ inside $r(\{ x_1, \ldots, x_n \})$, and these are all linearly independent.
A: No:  if we just have ZF, then we can not construct a basis for every $k(X)$.
From a basis we could prove the axiom of choice for sets of pairs, but Cohen proved that axiom independent of ZF in the same book where we proved independence for the usual AC (Set Theory and the Continuum Hypothesis, p. 142.)
[UPDATE:  This all depends on the meaning of "every $k(X)$ has a basis", roughly either:
$$\forall k\, \forall X\, \exists B\,\, \exists f:V \rightarrow \{(k_i),(b_i)\}\,\forall v \,\,v=\sum_{i=1}^n k_i b_i $$
or:
$$\forall k\, \forall X\, \exists B\,\, \forall v \, \exists k_1,\ldots,k_n, \exists b_1,\ldots b_n\,\, v = \sum_{i=1}^n k_i b_i$$
The proof goes through under the first interpretation, but not the second.]
Here is some intuition for the proof below.  A basis of $k(X)$, as standardly defined, gives any element of $k(X)$ as a finite sum of elements of $k$ times elements of the basis, which is to say a sum indexed by some $1...n$, which is to say an ordered sum.  So if $x$ and $y$ are elements of the basis, then we can choose between them by looking at the expression for $x+y$ in terms of the basis, and whether $x$ or $y$ appears first in that expression.  Even if $x$ and $y$ are not elements of the basis, we can still look at the expression for $x+y$ to see if it starts more like $x$ or more like $y$.
Proof of AC for pairs from the existence of a basis:  Let $k$ be an ordered field, and suppose we have a basis for $k(X)$.  We define a function $f:X\times X \rightarrow X$, where $f(x,y)$ is determined as follows:
Suppose $x,y$ are in $X$.  Write $x+y$ in terms of the basis for $k(X)$ as $\sum_{i=1}^m c_i v_i$.  Write $x$ in terms of the basis, as $\sum_{i=1}^n a_i v_i$, where some of the initial $a_i$ may be 0 and $n$ may be larger than $m$ if $x$ needs more basis elements.  Now we can write $x=\sum_{i=1}^n a_i v_i,\, y=\sum_{i=1}^n b_i v_i,\, x+y=\sum_{i=1}^n c_i v_i$.  
For some $i$, we may have $c_i = (a_i+b_i)\,/\,2$, and this is true for all $i>m$.  If that is true for all $i$ then $x+y=(x+y)\,/\,2$, so $x+y=0$, which is impossible.  So find the first $i$ for which $c_i$ is not $(a_i+b_i)\,/\,2$.  If $c_i$ is closer to $a_i$ then let $f(x,y)=x$, otherwise let $f(x,y)=y$.
Now $f(y,x)=f(x,y)$.  So therefore $f$ defines a choice function on the unordered pair $\{x,y\}$, QED.  
