As explained in Carl Mummert’s answer, there are decidable theories with nonrecursive models. To answer the first question, every decidable theory also has a recursive model, and in fact, a model with a recursive satisfaction predicate (or in other words, decidable elementary diagram). The reason is that the usual Henkin completion procedure provides a recursive construction of a complete Henkin extension $T^+$ of $T$ as long as $T$ is decidable, and then $T^+$ is essentially identical to the elementary diagram of its canonical model.
However, since your “nonstandard finite fields” are not all models of the relevant first-order theory (pseudofinite fields of characteristic $0$), but only models of a very special form (those that can be obtained as quotients of models of PA), this does not mean that there are recursive “nonstandard finite fields”. In fact, countable “nonstandard finite fields” are exactly the recursively saturated pseudofinite fields of characteristic $0$, and there are no recursive, recursively saturated pseudofinite fields, as shown by Macintyre.
I don’t see what quantifier elimination has to do with anything. Quantifier elimination for pseudofinite fields, namely that every formula is equivalent to a Boolean combination of formulas of the form $\exists y\,f(x_1,\dots,x_n,y)=0$, where $f$ is a polynomial with integer coefficients, can certainly be made effective (although its most convenient model-theoretic proofs are nonconstructive). This follows automatically from the fact that the theory of pseudofinite fields is recursively axiomatizable (actually even decidable). However, this does not imply anything about recursivity of its models. To begin with, whether a model is recursive only calls for recursivity of the basic relations and functions, not more complex formulas, so eliminating quantifiers from the latter won’t help.
While quantifier elimination does not help with the existence of (non)recursive models, or with recognizing recursive models, it does have implications for other properties of recursive models. Specifically, if a model of the theory is recursive, then its satisfaction predicate has bounded complexity. In the case at hand, every recursive pseudofinite field has a $\Delta^0_2$ (more precisely, tt-reducible to $\emptyset'$) satisfaction predicate. Even more is true: pseudofinite fields are model-complete in a language expanded with constants for coefficients of irreducible polynomials of each degree, and this implies that for any fixed formula $\phi(x_1,\dots,x_n)$ and a recursive pseudofinite field $F$, the relation $\{\langle a_1,\dots,a_n\rangle:F\models\phi(a_1,\dots,a_n)\}$ defined by $\phi$ in $F$ is recursive.
