Non-zero prime ideals in the ring of all algebraic integers

Yes, $\mathcal{O}$ has lots of prime ideals (the axiom of choice is equivalent to every non-unit in any commutative ring being contained in a maximal ideal).

A concrete example is not so easy, but the point is this: for any finite field extension $L/\mathbb{Q}$, pick a prime $\mathfrak{p}_L$ of the ring of integers $L$, and do so compatibly, i.e. if $L \subset L'$ we need $\mathfrak{p}_{L'} \cap L = \mathfrak{p}_L$. The union of all the $\mathfrak{p}_L$ will then be a prime.

We don't need the axiom of choice. We can write down a maximal ideal.

First, we observe that $R$ is countable: For every monic $p \in \mathbb{Z}[x]$ let $V(p)$ be the set of its complex roots. It has a canonical enumeration, when we order the roots using the lexicographic order on $\mathbb{R} \times \mathbb{R}$. For every $n \geq 1$ the set of these $p$ of degree $n$ identifies with $\mathbb{Z}^n$ and is therefore countable, with an explicit enumeration. It follows that also $\mathcal{O}_n = \cup_{\mathrm{deg}(p)=n} V(p)$ has an explicit enumeration, and then also $\mathcal{O}= \cup_n \mathcal{O}_n$. This enumeration is complicated, but it is computable.

Now let $R \neq 0$ be any countable ring. Any enumeration $R=\{a_0,a_1,\dotsc\}$ produces a maximal ideal as follows: Define an increasing chain of proper ideals $I_k$ as follows: Let $I_0=0$. If $I_k$ is already defined, and $I_k + \langle a_k \rangle$ is proper, let $I_{k+1} = I_k + \langle a_k \rangle$. If not, call $a_k$ bad, and let $I_{k+1}=I_k$. Then $I:=\cup_k I_k$ is a maximal ideal: By construction $1 \notin I$. Now let $a_k \in R \setminus I$. Then $a_k$ has to be bad (otherwise $a_k \in I_{k+1} \subseteq I$), so that $I_k + \langle a_k \rangle = R$ and hence $I+\langle a_k \rangle = R$. $\square$

More generally, let $R$ be a ring $\neq 0$ whose underlying set is well-orderable. Every enumeration $R=\{a_{\alpha} : \alpha < \kappa\}$ with some limit ordinal $\kappa$ produces a maximal ideal (without using the axiom of choice): Let $I_0=0$, and construct $I_{\alpha+1}$ from $I_{\alpha}$ as above. For limit ordinals $\lambda<\kappa$, let $I_{\lambda}=\cup_{\alpha<\lambda} I_{\alpha}$. Then $I=\cup_{\alpha<\kappa} I_{\alpha}$ is maximal: If $\alpha<\kappa$ and $a_{\alpha} \notin I$, then $a_{\alpha}$ is bad (otherwise $\alpha+1<\kappa$, $a_{\alpha} \in I_{\alpha+1} \subseteq I$), hence $I_{\alpha}+\langle a_{\alpha} \rangle = R$ and $I+\langle a_{\alpha} \rangle = R$.

Even more generally, the proof of "well ordering principle $\Rightarrow$ Zorn's Lemma" in ZF actually shows that every partial order, in which every chain has an upper bound, and whose underlying set is well-orderable, has a maximal element.

This is not a "constructive" proof, but is certainly a very short one: if an integral domain has $(0)$ as its only prime ideal, then it is a field. But $\mathcal O$ is obviously not a field: for instance, $2$ is not invertible in $\mathcal O$.