Can we have stratified L? Can one build a hierarchy of stratified constructible stages? That is a hierarchy that is built in a manner similar to Godel's constructible universe L, but with additionally requiring that the defining formulas must be also stratified!

If that can be built, then my main question is whats the stance of choice in that hierarchy, would choice be satisfied internally in every limit stage of that hierarchy? Can choice fail?

 A: Glad to see someone taking an interest in this stuff!
All but one of the Goedel operations are stratified, and the one that isn't is the existence of $\in$ "locally."  Replace this operation by one that gives you the local version of $\in$ composed with singleton, so that you get
$A \cap \{\langle \{x\},y \rangle: x \in y \in B\}$.  You can then prove an exact analogue of the original result that anything closed under the rudimentary functions and power set is a model of $\Delta_0$ separation - for the stratified operations.  Any set closed under the stratrud functions and power set is a model of stratified $\Delta_0$ separation.  This actually gives a finite axiomatisation of NF.  Naturally one wonders about what happens if one tries to construct an analogue of $L$ in the fashion and the (annoying) answer is that what one gets depends very sensitively on how often one "sweeps up."  The more often you sweep up the more of $L$ you get.  I have some quite extensive notes on this, but they are from about 10 years ago and i would need to do some archaeology.  I will if pressed.
A: My original answer was quite wrong. The present answer is intended to highlight the issue I got tripped up on.
For any set $\Phi$ of formulas we can consider the "iterated $\Phi$ comprehension" analogue of $L$, which I'll call "${}^\Phi L$," defined in the obvious way: ${}^\Phi L_0=\emptyset$ and we take unions at limit levels, and ${}^\Phi L_{\alpha+1}$ is the set of all subsets of ${}^\Phi L_\alpha$ definable using formulas from $\Phi$ (with parameters from ${}^\Phi L_\alpha$ allowed).
While we do have ${}^\Phi L=L$ whenever $\Phi$ is strong enough to define the Godel operations, the set $\mathsf{strat}$ of stratified formulas is not such a $\Phi$, the culprit operation being $\mathfrak{F}_2$. So the following remains open (contra the previous version of this answer):

Is ${}^\mathsf{strat}L=L$?

Forster has introduced his own "stratified analogue" $Sr$ of $L$ (although on a couple occasions Forster uses "$S$" instead). However, his construction is via a modification of the usual list of Godel functions, so I also don't see the answer to the following question:

Is ${}^\mathsf{strat}L=Sr$?

Certainly ${}^\mathsf{strat}L$ lies between $Sr$ and $L$, but that's not very interesting.  I suspect that in fact we do have ${}^\mathsf{strat}L=Sr$, but at the moment I don't see the proof. Note that Forster shows $Sr\not\models\mathsf{AC}$, so this would answer the OP's question.
