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!
Yes, you can remove the axiom of foundations by the same argument: move from a universe of $\sf ZF-Fnd$ to the von Neumann universe, which is the largest well-founded and transitive class.
When you remove Infinity, Power set, or Replacement, you get strictly weaker theories. To see why, note that $V_\omega,\mathrm{HC}$ and $V_{\omega+\omega}$ are models of $\sf ZF-Infinity, ZF-Power, ZF-Replacement$ respectively. Therefore $\sf ZF$ proves these theories have a model, so they are consistent. In particular by Gödel's theorem none of them can prove that $\sf ZF$ itself is consistent.
Best Answer
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.