Towards a partial answer:

I have not read it myself yet, but it seems that the relative consistency of $\mathsf{AC}$ with $\mathsf{Z}$ was proved by Mathias in his paper *The strength of MacLane set theory*. To quote Mathias' summary (available here):

The paper shows that Z + AC is indeed consistent relative to Zermelo's system Z, but the inadequacy, demonstrated in Slim Models, of Z for recursive constructions necessitates an oblique approach.

Of course this leaves open the question of whether $\neg\mathsf{AC}$ is also relatively consistent with $\mathsf{Z}$. In the absence of replacement, forcing becomes quite tricky, so the "usual" approach seems fraught to say the least. Mathias has intensely studied forcing over weak set theories (leading up to his analysis of and advocacy of "provident set theory" $\mathsf{Provi}$ in this context), but at a quick glance I don't see any results that suffice here. I suspect, though, that the answer is again affirmative.