Let $\alpha > \omega$ and $u = \{\ulcorner \sigma \urcorner : \sigma \in \mathrm{Th}(\mathbb{L}_\alpha, \in)\} \subseteq \omega$, where by $\mathbb{L}_\alpha$ we denote as usual the constructible sets up to level $\alpha$.
My question is "Can we have $u \in \mathbb{L}_\alpha$?".
Suppose we can. Let $\phi(x) := x \in u$. Then for every sentence $\sigma$ we have that $$\mathbb{L}_\alpha \models \phi(\ulcorner \sigma \urcorner) \Leftrightarrow \mathbb{L}_\alpha \models \sigma,$$ i.e. truth is definable in $(\mathbb{L}_\alpha, \in)$, which contradicts the incompleteness theorem.
So $\mathscr{P}(\omega) \nsubseteq \mathbb{L}_\alpha$ for all $\alpha \in \mathrm{ON}$.
Note that the same can apply with the universe of set theory:
For example let $u=\{\ulcorner\sigma\urcorner : \sigma\in\mathrm{Th}(V_\alpha,\in)\}\subseteq\omega$. Then for $\alpha>\omega+1$ we have that $u\in V_\alpha$. Then the formula $x\in u$ yeilds $$V_\alpha\models\ulcorner\sigma\urcorner\in u\iff V_\alpha\models\sigma$$ i.e. there is nothing special about the constructible universe.
The problem with the argument is that the formula $x\in u$ is not definable from the language of the model (i.e. $\{\in\}$), but from the language with an extra constant term $u$. The model may not be able (in fact by Tarski's theorem it is not able) to define -using its language- the set $u$, creating no conflict with Tarski's theorem.
The subsets of $\omega$ that you describe are always in $\mathbb{L}$ since they are definable with parameters from $\mathbb{L}_{\alpha+2}$ for example. They are simply not definable in $\mathbb{L}_\alpha$.
As an interesting aside (that Jech notes), if $0^\sharp$ exists then the theory of $\mathbb{L}$ is the same as that of $\mathbb{L}_{\aleph_1}$, so the theory of $\mathbb{L}$ is an element of $\mathbb{L}$. This means that in that case the real $\aleph_1$ is not definable in $\mathbb{L}$, making it quite large.