Partial answer: $1\Rightarrow2\Rightarrow3\Rightarrow (2$ for compact metrizable spaces)
It will be convenient to consider also a fourth characterization, the (von Neumann-)Dixmier criterion:
4) if $K\subset G$ is finite and $f_k\in B(G)$, $k\in K$, we have $\displaystyle\inf_G\sum_{k\in K}(f_k-f_k\circ\ell_k)\le0$, where $\ell_g(x)=gx$ (left-translation).
This is an easy consequence of the Følner criterion 3, and as that one it obviously holds for $G$ if and only if it holds for every finitely generated subgroup (all this in ZF). Finally, for finitely generated groups, Følner implies Dixmier using Hahn-Banach for a separable Banach space, thus in ZF.
Proof of $1\Rightarrow2$ (for any discrete group). If $\mu$ is a left-invariant finitely additive probability measure on $G$, one associates to it a left-invariant mean $m(f)=\displaystyle\int_Gf(g)d\mu(g)$ defined on all bounded functions of $G$: $m(f)=\sup \displaystyle\sum_{\lambda\in\bf R}\lambda\mu(\varphi^{-1}(\lambda)\})$ over every function $\varphi\le f$ taking only finitely many values.
Then if $G$ acts on a compact space $X$, we construct a Radon probability measure which is left-invariant, or equivalently a positive linear form $p$ on $C(X)$ such that $p(1_X)=1$ and $p(f\circ\ell_g)=p(f)$ where $\ell_g$ is the left-translation by $g$: choose $x_0\in X$ and set $p(f)=m(\gamma\mapsto f(\gamma.x_0))$. Then
$$\eqalign{p(f\circ\ell_g)&=m(\gamma\mapsto f((g\gamma).x_0)\cr
&=m(\gamma\mapsto f(\gamma.x_0))\ \hbox{by left-invariance}\cr
&=p(f).\cr}$$
Proof of $2\Rightarrow 4$ (inspired by A. Paterson, Amenability, Problem 2-14 p.90, solution p. 420) We take now $B(G)$ to be the bounded complex functions on $G$. Let $A\subset B(G)$ be the $C^*$-algebra generated by $f_1,\cdots,f_n$. In other words, $A$ is the norm-closure of all polynomials in $f_1,\cdots,f_n,\overline f_1,\cdots,\overline f_n$. It is a separable commutative unital $C^*$-algebra, thus by the Gelfand representation theorem it is isomorphic to $C(X)$ for $X$ a compact metric space, this in ZF because of separability.
The action of $G$ on itself by left translations gives rises to an action on $X$ such that $f(g.x)=(g^{-1}f)(x)$. By hypothesis this action has an invariant Borel (here it the same as Radon) probability measure, ie $A$ admits an invariant positive linear form $p$ such that $p(1)=1$. By invariance, $p(\displaystyle\sum_{k\in K}(f_k-f_k\circ\ell_k))=0$, which implies (by positivity) $\displaystyle\inf_G\sum_{k\in K}(f_k-f_k\circ\ell_k)\le0$.
Proof of $3\Rightarrow 2$ for a compact metrizable space. If $X$ is a compact metrizable space, the space of Radon (= Borel here) probability measures $P(X)$, viewed as a subspace of $C(X)^*$ with the weak $*$-topology, is compact (and metrizable). This is true in ZF since it is contained in $[-1,1]^D$ where $D$ is a countable dense subset of the unit sphere of $C(X)$, and Tychonov's theorem in this case is true in ZF. By the Følner criterion, for every $K\subset G$ finite and $\varepsilon>0$ there existe a non-empty finite set $F\subset G$ such that $\displaystyle\max_{k\in K}|F\setminus kF|\le\varepsilon|F|$. Then, if $x_0\in X$ is fixed, $p=\displaystyle{1\over|F|}\sum_{g\in F}\delta_{g.x_0}$ belongs to the set
$$F_{K,\varepsilon}=\{p\in P(X):\max_{k\in K}||p-p.g||\}\le2\varepsilon\}.$$
The family $(F_{K,\varepsilon})$ consists of closed sets and has the finite intersection property since $\displaystyle\bigcap_{i=1}^nF_{K_i,\varepsilon_i}\supset F_{K_1\cup\cdots\cup K_n,\min\varepsilon_i}$. Thus its full intersection is nonempty, and it consists of the invariant probability measures.
Remarks. (i) The last proof holds whenever $P(X)$ is compact for the weak $*$-topology. I do not know if $X$ compact implies $P(X)$ compact in ZF. If not, presumably $3\Rightarrow 2$ does not hold in general.
(ii) Things get better with many (all ?) other characterizations of amenability. For instance, consider the Markov-Kakutani fixed point property:
5) every $G$-space $X$ which is compact, affine and convex has a fixed point.
Proof of $3\Rightarrow 5$. Fix $x_0\in X$. If $F\subset G$ is a $(K,\varepsilon)$-Følner set, the point $x=\displaystyle{1\over|F|}\sum_{g\in F} g.x_0$ belongs to the set
$$F_{K,\varepsilon}=\{x\in X:(\forall k\in K)\ x-kx\in[-\varepsilon,\varepsilon]K\}.$$
The family $(F_{K,\varepsilon})$ consists of closed sets and has the finite intersection property since $\displaystyle\bigcap_{i=1}^nF_{K_i,\varepsilon_i}\supset F_{K_1\cup\cdots\cup K_n,\min\varepsilon_i}$. Thus its full intersection is nonempty, and it consists of the fixed points.
Proof of $5\Rightarrow 4$. This is essentially the same proof as $2\Rightarrow 4$.
