[continued...]
There is a standard way of constructing non-Borel sets, which is mentioned in, e.g., Cohn, Measure Theory (Corollary 8.2.17) and, even without countable choice, the argument still works to give you a non-codable-Borel set. It is a diagonalization kind of argument. This constructs a subset of Baire space $\mathcal{N}=\mathbb{N}^\mathbb{N}$ (under the product topology). This is a Polish space homeomorphic to the irrational numbers in [0,1] by the continued fraction representation (I'm taking $\mathbb{N}=\{1,2,\ldots\}$ for convenience).
If X,Y are Polish spaces, then say a subset $S\subseteq X\times Y$ is universal if every closed subset of X is of the form $S_y=\{x\in X\colon(x,y)\in S\}$. It is always possible to construct a closed universal subset of $X\times\mathcal{N}$. If $U_1,U_2,\ldots$ is an enumeration of a base for the topology on X, then
$$
S=\left\{(x,y)\in X\times\mathcal{N}\colon x\in\bigcap_{n=1}^\infty U_{y(n)}^c\right\}
$$
is closed and universal.
Now, take S to be a closed universal subset of $X\times\mathcal{N}$ where $X=\mathcal{N}\times\mathcal{N}$.
The set $A=\{x\in\mathcal{N}\colon
> \exists y\in\mathcal{N}{\rm\ s.t.\ }
> (x,y,x)\in S\}$ is an analytic but
non-codable-Borel subset of
$\mathcal{N}$.
A subset of a Polish space X is analytic if it is the projection of a closed subset of $X\times\mathcal{N}$ onto X. The set A above is the projection of the set $\{(x,y)\in\mathcal{N}^2\colon(x,y,x)\in S\}$, so is analytic. If it was codable Borel, then its complement would be the projection of some closed set $B\subseteq\mathcal{N}^2$. By universality, $B=S_x$ for some $x\in\mathcal{N}$. However,
$$x\in A^c\iff \exists y{\rm\ s.t.\ } (x,y)\in S_x \iff \exists y{\rm\ s.t.\ }(x,y,x)\in S\iff x\in A$$
would give a contradiction.
In fact, I think I can show that the set you linked to by Lusin is not codable Borel, without using choice. By continued fraction representation, it is the same as saying that the following is not codable Borel.
S = the set of $x\in\mathcal{N}$ for which there is an increasing sequence $0\lt i_1\lt i_2\lt\cdots$ such that each $x(i_k)$ divides $x(i_{k+1})$.
In the presence of choice, this is standard (Kechris, Classical Descriptive Set Theory has a proof, but I don't have a copy). I expect that the proof can be adapted in the absence of countable choice but, as I don't know the standard proof of this, I can give a very very rough sketch of my own. The idea is to consider the set of trees $\mathcal{T}$, where each node has a countable set of children corresponding elements of $\mathbb{N}$. Any such tree is defined by the set of finite paths $(i_1,\ldots,i_n)\in\mathbb{N}^*=\bigcup_{n=1}^\infty\mathbb{N}^n$ it contains, and $\mathcal{T}$ forms a Polish space (using the product topology on $\{0,1\}^{\mathbb{N}^*}$). Let $\mathcal{T}_0\subseteq\mathcal{T}$ be the trees containing no infinite paths. These correspond to the Borel codes. Then, $\mathcal{T}_0$ is itself not codable Borel (*). Next, each tree can be represented uniquely by an element $x\in\mathcal{N}$ in such a way that passing from a node to one of its children corresponds to going from i to $j\gt i$ where $x(i)$ divides $x(j)$. Then, $\mathcal{T}_0$ correponds precisely to the set S above which, therefore, is not codable Borel.
(*) That $\mathcal{T}_0$ is not Borel is standard (in the presence of AoC). I don't know the proof of this, maybe it can be shown using a similar argument to the one above for non-analytic sets. However, I can put together an alternative rough argument of my own that it is not codable Borel. The idea is that each tree corresponds to a program for some super-Turing machine which can perform countable Boolean operations at once, and those without infinite paths are guaranteed to halt. If $\mathcal{T}_0$ was codable, then there would be a Borel code $T\in\mathcal{T}_0$ which generates $\mathcal{T}_0$. This is similar to having a Turing program which solves the halting problem, and we could derive a contradiction in a similar way. There are some messy details in getting this analogy to go through properly, but it seems like it should work.
