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}$).
EDIT: to my chagrin, the notion of "$n$-admissibility" is not what I thought it was! What I wanted was $\Sigma_n$-admissibility. You can find the definition of $n$-admissibles here; they are vastly smaller than their $\Sigma_n$ counterparts, and indeed for each $n$ the least $n$-admissible is less than the least $\Sigma_2$-admissible. Now $n$-admissibility is a rare notion these days and I've seen "$n$-admissible" used for "$\Sigma_n$-admissible before, but given the relevance of older papers to this topic it's probably a good idea for me to not butcher this distinction.
All limit levels of $L$ beyond $\omega$ satisfy the "basic" axioms (extensionality, foundation, pairing, union) plus choice trivially; once you drop powerset, you're really just talking about replacement/separation.
An infinite limit ordinal $\alpha$ is $\Sigma_n$-admissible if $L_\alpha$ satisfies $\Sigma_n$ replacement; $\Sigma_1$-admissibility is just normal admissibility, and one way to define $\omega_1^{CK}$ is as the smallest admissible ordinal $>\omega$.
So what you're looking for is just the smallest $\Sigma_\omega$-admissible ordinal, where an ordinal is $\Sigma_\omega$-admissible if it's $n$-admissible for each $n$.
Now it's worth stressing that the smallest $\Sigma_{n+1}$-admissible is much, much, much larger than the smallest $\Sigma_n$-admissible. The first admissible limit of admissibles is extremely large (much bigger than the first limit of admissibles) and is still drastically smaller than the first $\Sigma_2$-admissible.
Incidentally, note that ZFC proves that $L_{\omega_1}$ (exists and) is a model of all of ZFC except powerset. From this we get $\beta<\lambda$, and indeed $\beta<(\omega_1)^{L_\lambda}$ (inside $L_\lambda$, take the Mostowski collapse of a countable elementary submodel of $(L_{\omega_1})^{L_\lambda}$). Put another way:
Not only is $\beta<\lambda$, we have $L_\lambda\models$ "$\vert\beta\vert=\aleph_0$."
(Keep in mind that $L_\lambda\models$ "There is no largest cardinal," so this is really quite a size difference!)
Best Answer
Such an object is complicated to describe, but not too complicated. In general, the appearance of reals throughout $L$ is technical but not mysterious: we sort of keep using the same basic tricks over and over again. Standard go-to's include countability witnesses and first-order theories of countable levels of $L$ and related structures; common techniques include Lowenheim-Skolem, the condensation lemma (and the Mostowski collapse), and the use of the $L$-ordering to eliminate parameters.
First, there is a general approach that applies more-or-less to every countable ordinal. Whenever $\alpha$ is countable, so is $L_\alpha$, which means there is a (not unique of course) relation $R\subseteq\omega^2$ such that $(\omega; R)\cong (L_\alpha;\in)$ (I'm assuming $\alpha$ is infinite, here). However, it's easy to see that such an $R$ can never, itself, be in $L_\alpha$. That is, for every countable $\alpha$ there are reals which code bijections between $L_{\beta_0}$ and $\omega$, none of which are in $L_\alpha$, and particular this is true for $\alpha=\beta_0$.
We can further identify a specific such real (using $\alpha$ as a parameter): the least real with respect to the parameter-freely-definable well-ordering of $L$ which codes a bijection between $\omega$ and $L_\alpha$. In case $\alpha$ itself is parameter-freely definable - as $\beta_0$ is - this real is also parameter-freely definable. (We can also give a quick complexity analysis: for ordinals such as $\beta_0$ corresponding to the first level of $L$ satisfying a given first-order theory, the resulting definition is $\Delta^1_2$.)
A more specific argument would be to observe that - conflating a transitive set $A$ with the corresponding $\{\in\}$-structure $(A; \in\upharpoonright A)$ - the structure $L_{\beta_0}$ happens to be a pointwise definable structure; that is, each element in it is definable without parameters in it. This means that $Th(L_{\beta_0})$, the set of Godel numbers of all $\{\in\}$-sentences which are true in $L_{\beta_0}$, is not itself an element of $L_{\beta_0}$.
But this relies on particular properties of $\beta_0$; there are many countable ordinals $\gamma$ such that $L_\gamma$ is not pointwise-definable; indeed, most countable ordinals have this property, in the sense that the set of $\gamma$ such that $L_\gamma$ is not pointwise definable is club. Such an $L_\gamma$ can indeed contain its theory as an element, avoiding Tarski by way of that specific element not being parameter-freely definable. For example, $L_{\omega_1}$ contains every real in $L$, including (since $L$ computes first-order theories correctly) the theory of $L_{\omega_1}$ itself. And we can bring this down to the countable realm too, by applying Lowenheim-Skolem, Mostowski collapse, and condensation to get a countable $\gamma$ such that $L_\gamma\equiv L_{\omega_1}$ and $Th(L_{\omega_1})\in L_\gamma$ (hence $Th(L_\gamma)\in L_\gamma$ since $L_\gamma\equiv L_{\omega_1}$).
Incidentally, if you're not already familiar with it you'll probably be interested in the paper "Gaps in the constructible universe" by Marek and Srebrny.