You cannot construct what is not there.
When we construct the real numbers from the rational numbers, we don't invent them out of thin air. We use material around us: sets of rational numbers (or sets of functions which are sets of sets of rational numbers). And similarly when we want to construct a dual vector space, we don't wave our hands and whisper some ancient texts from the Necronomicon ex Mortis. We use the sets at our disposal (and the assumptions they satisfy certain properties) to show we can define a structure with the wanted properties.
So the real numbers, and dual vector spaces, and all the other mathematical constructions, have existed in your fixed universe of sets before you began your work. What we do, if so, is not as much as constructing as we are defining them and using our axioms to argue that as the definition "makes sense" (whatever that means in the relevant context), such objects exist.
"Okay, Asaf, but what does all that have to do with my question?", you might be asking yourself, or me, at this point. Well, if you don't interrupt me, I might as well tell you.
The von Neumann universe is a way to represent a universe of $\sf ZF$ as constructed from below. But it is using the pre-existing sets of the universe. What is clever in this construction is that it exhaust all the sets of the universe. And if the universe only satisfied $\sf ZF-Reg$, then the result is the largest transitive class which will satisfy $\sf ZF$.
But what happens in different models of set theory? Well, we can prove from $\sf ZF$ that the von Neumann hierarchy, which has a relatively simple definition in the language of set theory, exhausts the universe. So each different model will have a different von Neumann hierarchy. And models which are not well-founded, will have a non-well-founded von Neumann hierarchy.
So yes, we first need a model of $\sf ZF$ in order to construct this hierarchy, but we don't need it inside the theory. We need it in the meta-theory. Namely, if you are working with $\sf ZF$, then you most likely assume it is consistent in your meta-theory, where you formalize your arguments and do things like induction on formulas. And that is enough to prove the existence of the von Neumann hierarchy; because once you work inside $\sf ZF$, the whole universe is given to you!
The argument is clearly wrong. $\mathcal P(\omega)$ is definable without parameters, and yet it is not necessarily constructible, as shown by Cohen.
The thing to remember is that the formula $\phi$ is not absolute between models. So $\mathcal P(\omega)$ and $\mathcal P(\omega)^L$ might be different.
In some cases, there are sets whose definition is very robust and unique, but they cannot even exist in $L$. One example of this kind is $0^\#$, which has a parameter free definition, and can be represented as a fairly canonical set of integers. But nevertheless, this set cannot exist in $L$. Other examples would be any real, since you can code it into the continuum pattern below $\aleph_\omega$ (for example), and even much more than that.
Best Answer
As discussed in the comments, the notion of a set which a theory proves exists is inherently problematic, and it's difficult to formulate a version of the requirement "All sets which we can prove exist, can be proved to be in $L$" which doesn't fail for silly reasons.
It seems to me, though, that the following is probably the strongest theory which will match the intuitions behind such a requirement:
First, we take the usual axioms of ZFC and relativize them to $L$. So, for example, Powerset becomes "For every constructible $x$ there is a constructible $y$ such that for every constructible $z$, if every constructible element of $z$ is in $x$ then $z$ is in $y$, and every constructible element of a constructible element of $y$ is in $x$."
Now the resulting theory $ZFC^L$ is fine: any model of it has a definable subset which is a model of ZFC+V=L. However, by relativizing everything we've made stuff a bit weird. For example, the rest of such a model could be truly awful, and the "$L$-part" itself might not sit nicely in the whole (e.g. it might not be transitive). So we probably want to pass to a stronger theory $ZFC^L_+$, consisting of $ZFC^+$ together with unrelativized Extensionality, Union, Pairing, and Foundation, and an axiom asserting that the ordinals of $L$ are exactly the ordinals of the universe.
The result is a theory all of whose models satisfy a very weak set theory, but which have an inner model satisfying ZFC+V=L. And this seems as close to what you want as I can think of.