Below I've addressed your specific questions. However, based on your multiple questions about this I think it might be more useful to give a list of good sources, so I'll do that first.
On "gaps" in the constructible universe: Marek/Srebrny, Gaps in the constructible universe. The introduction is very readable and will give you a good sense of what's going on.
On the mastercode hierarchy (and what happens when new reals do appear): Hodes' paper Jumping through the transfinite. This is also closely connected with the study of gaps. Like the paper above, the introduction is a very good read.
On the general structure of $L$: Devlin's book Constructibility. It has a serious error unfortunately, but that error doesn't affect the important results; see this review by Stanley for a summary of the issue (and if you're interested in how to correct it, this paper by Mathias). Ultimately the error is very limited and easily avoided once you know it exists - basically, doubt anything involving a claim about the (aptly named) set theory "BS," but pretty much everything else is correct.
Now, it would seem that every one of these sets could in principle be defined in first order logic without parameters (though I am unsure how this would work in practice)
There's no subtlety here: we first define addition and multiplication of finite ordinals, and now we can use port the usual definitions in $(\mathbb{N}; +,\times)$ of those sets into the set theory context. Indeed, there's a natural way (the Ackermann interpretation) to pass between $L_\omega$ and $(\mathbb{N};+,\times)$, so definability in $L_\omega$ can be reasoned about by proving things in the more familiar setting of definability in arithmetic; e.g. this lets us argue that the Busy Beaver function is indeed in $L_{\omega+1}$.
would a non-constructible real (assuming its existence) be in some sense infinitely complex in that it could not be described in any form whatsoever, either directly, or via some cumulative process?
Certainly not: e.g. $0^\sharp$ is definitely definable (it's $\Delta^1_3$, and in particular is definable in second-order arithmetic) but is not in $L$ (assuming it exists at all). ZFC can't prove that something matching the definition of $0^\sharp$ exists, but it can prove that if it exists then it's not constructible.
Given a particular countable ordinal $\alpha$, can we always find (by which I mean, explicitly describe) a real X with L-rank $\alpha$?
No; for many (indeed, club-many) ordinals $<\omega_1^L$, we have no new reals at that level. Indeed, the $L$-hierarchy is "filled with gaps" - even very long gaps. If you google "gaps in $L$-hierarchy" you'll find a lot of information around this; roughly speaking, an ordinal $\alpha<\omega_1^L$ starts a "long" gap if it is "very" similar to $\omega_1^L$.
In terms of complexity, the reals clearly become more complex as their $L$-rank increases, but is there a way to formalize this precisely?
Well, the obvious one is that if $A$ has $L$-rank greater than that of $B$, then the set $A$ is not definable in the structure $(\mathbb{N}; +,\times, B)$ (that is, arithmetic augmented by a predicate naming the naturals in $B$). In particular $A\not\le_TB$. On the other hand, $A$ might not compute $B$ either (e.g. if $A$ is "sufficiently Cohen generic" over $L_\beta$ then $A$ won't compute any noncomputable real in $L_\beta$ - in particular, it won't compute any real in $L_\beta$ not in $L_{\omega+1}$).
It is consistent that there is no such $\alpha$.
More precisely, it is consistent with ZFC that there is a formula $\varphi$ in the language of second-order arithmetic such that $\{x:\varphi(x)\}$ is not constructible. For example, $0^\sharp$ if it exists has this property (it's $\Delta^1_3$-definable if it exists).
EDIT: Of course, if V = L then such an $\alpha$ trivially exists. Throughout the rest of this answer we assume V=L.
The key point is that there is a "definable translation" between first-order formulas over $L_{\omega_1}$ and second-order formulas of arithmetic:
One direction is immediate: any second-order arithmetic formula can be rephrased in $L_{\omega_1}$ since sets of naturals are already elements of $L_{\omega_1}$.
The other direction is the interesting one. Given a well-founded tree $T\subset\omega^{<\omega}$ (note that we can definably conflate subsets of $\omega$ and subsets of $\omega^{<\omega}$, and that the set of well-founded trees is second-order definable), we recursively define a map $Set_T$ from nodes of $T$ to sets, by setting $$Set_T(\sigma)=\{Set_T(\sigma^\smallfrown \langle k\rangle): k\in\omega, \sigma^\smallfrown\langle k\rangle\in T\};$$ for example, if $\sigma$ is a leaf of $T$ then $Set_T(\sigma)=\emptyset$. We then let $Set(T)=Set_T(\langle\rangle)$ be the set assigned to the empty string (= the root of $T$). It's easy to check that the relations "$Set(T_0)=Set(T_1)$" and "$Set(T_0)\in Set(T_1)$" are definable in second-order arithmetic, and this gives us an interpretation of $L_{\omega_1}$ into $\mathcal{P}(\omega)$.
The projectively-definable reals are precisely the parameter-freely definable elements of the first-order structure $(\omega,\mathcal{P}(\omega); +,\times,\in)$, and the translation above identifies these with the set $M$ of parameter-freely definable elements of the first-order structure $(L_{\omega_1}; \in)$ (which I'll conflate with $L_{\omega_1}$).
The final point is that since $L$ has definable Skolem functions, $M$ is in fact an elementary submodel of $L_{\omega_1}$ and hence$^1$ $M=L_\eta$ for some $\eta$. This $\eta$ is exactly our $\alpha$. That is:
Assuming V=L, $\alpha$ is the height of the smallest elementary submodel of $L_{\omega_1}$.
In particular, this is massively bigger than $\beta_0$, since $\beta_0$ is parameter-freely definable in $L_{\omega_1}$.
$^1$This is a cute fact. The Condensation Lemma alone doesn't kill this off: in order to apply Condensation we need to know that $M$ is transitive. But a priori, it's not clear that it needs to be - for example, a countable elementary submodel of $L_{\omega_2}$ obviously can't be transitive, since it must contain $\omega_1$ as an element.
So what's special about $\omega_1$ here? The trick here is the following:
Suppose $A$ is a "sufficiently closed" transitive set (= contains $\omega$ and such that eveyr countable element of $A$ is countable within $A$) - for example, $A=L_{\omega_1}$ - and $B$ is an elementary substructure of $A$ (conflating a transitive set with the corresponding $\{\in\}$-structure as usual). Then the set of countable ordinals in $A$ is closed downwards.
Rough proof: Suppose $\theta$ is a (WLOG infinite) countable ordinal in $A$ and $\gamma<\theta$. Since $A$ computes countability correctly we have in $A$ an $f: \omega\cong\theta$. By elementarity "going down," $B$ contains some $g$ which $B$ thinks is a bijection from $\omega$ to $\theta$; by elementarity "going up," $A$ also thinks $g$ is. So (working in $A$) there is some $n\in\omega$ such that $g(n)=\gamma$; but since $n\in\omega$ we have $n\in B$ (we can't "lose" natural numbers!) and so $g(n)=\gamma\in B$ as well. $\Box$
We can generalize the above observation using further closedness assumptions: e.g. if $B$ is an elementary submodel of a sufficiently closed transitive set $A$ with $\omega_1\subseteq B$ then $B\cap\omega_2$ is closed downwards (running the above argument, we only need that $dom(g)\subset B$).
Best Answer
Your confusion is rooted by the mistake that being constructible does not mean being definable.
It is true that the constructible hierarchy constructs each step by taking definable subsets. But just because a set is definable over one structure doesn't mean it is definable over a different one. Not to mention, that the definable subset are taken with parameters anyway.
The point, in summary, is that being constructible means that you are definable with parameters over some initial segment of the hierarchy. But since there are many initial segments in which subsets of $\omega$ (or any ordinal) are added, there are uncountably many sets and all is fine.
Also, note that for $\omega$ to have uncountably many subsets, you don't need subsets of $\omega$ with rank at least $\omega_1$, just that for unboundedly many ordinals below $\omega_1$, we add new subsets to $\omega$. This is indeed what happens.