A countable entourage base can be replaced in ZF by a decreasing symmetric base whose next triple composite lies in the preceding member

Use the finite listing or bijection supplied by countability to write the given base as $(C_n)$, repeating its last member in the finite case. Put $B_n=\bigcap_{i\le n}(C_i\cap C_i^{-1}).$ Then $(B_n)$ is a canonically defined decreasing symmetric cofinal base.

Define indices recursively. Put $r_0=0$, and let $r_{n+1}$ be the least $k>r_n$ such that $B_k^{\circ3}\subseteq B_{r_n}$; then put $E_n=B_{r_n}$.

Each required set of indices is nonempty: choose a symmetric entourage $D$ with $D^{\circ3}\subseteq B_{r_n}$, then use cofinality and decreasingness to find $k>r_n$ with $B_k\subseteq D$. Thus the recursion is defined. The inequalities $r_{n+1}>r_n$ give decreasingness and cofinality, while the defining clause gives triple control.

Therefore $(E_n)$ is the asserted normal base in ZF.