Complexity of solving systems of linear equations with hash preimages
It depends what you mean by "arbitrary cryptographic hash function".  If you care about practical cryptography, I think the most natural interpretation is to model $H$ as a random oracle (i.e., the random oracle model for hash functions).

In this setting, the problem is hard.  As a lower bound, it requires exponential running time.

To prove this, let $u=(1,2,4,\dots,2^{n-1})$ and let $A$ be a $n\times n$ matrix of rank $n-1$ such that $\operatorname{Ker} A$ is spanned by $u$.  (Such a matrix exists.)  Let $c=0$.  Then the problem amounts to: find a constant $\alpha \in \mathbb{Z}$ such that $x=\alpha u$ and $H(x_i)=z_i$ for $i=1,\dots,n$.  Treating $H$ as a random oracle, any candidate value of $\alpha$ has a $1/d^n$ chance of meeting all the $H(x_i)=z_i$ requirements, where $d$ is the size of the range of $H$; so you'll need to try about $d^n$ different values of $\alpha$ before finding the first that is satisfactory [*].  The size of all integers is at most $n \log d = \Theta(n)$ bits, so the time to try each is polynomial.  Thus, the total running time is $2^{\Omega(n)}$ for this case.

I don't know what the complexity is.  I suspect that for a random matrix $A$ you might be able to solve this by enumerating solutions to $Ax=c$.  You can enumerate solutions using Hermite normal form.  This equation has either 0 solutions, 1 solution, or infinitely many solutions.  If it has no solutions, you can immediately conclude that your problem has no solutions.  If it has 1 solution, you can find it with Hermite normal form and then test whether it meets your $H(x_i)=z_i$ requirement.  If it has infinitely many solutions, you can use Hermite normal form to sample from the space of all solutions and check for each whether it satisfies all of the constraints.  There are degenerate cases where this approach might be very inefficient or may never terminate. I suspect for a random matrix $A$ it will typically take at most exponential time, but I have no proof of this.



Alternatively, suppose you intended for "arbitrary cryptographic hash function" to mean that $H$ is an arbitrary function from the integers to a finite domain.  I'll assume $H$ is represented as an oracle.

In this case, the problem is undecidable: there is no algorithm that is guaranteed to always terminate and always output the correct answer.

To show this, it suffices to consider the one-dimensional case, $n=1$, where $A=0$, $c=0$, $z=1$.  Then the problem amounts to: find $x \in \mathbb{Z}$ such that $H(x)=1$.  Consider running the algorithm with the hash function $H_0$ defined by $H_0(x)=0$ for all $x$.  Let $m$ be the largest number that is queried to the oracle (i.e., the largest number that we use as input to $H_0$) when the algorithm is run with $H_0$.  Define $H_1$ by $H_0(x) = 0$ if $x\le m$, or $1$ otherwise.  Then the algorithm's behavior on $H_0$ and $H_1$ is identical, so the algorithm is wrong on at least one of those two.



If neither of those capture what you intended by "arbitrary  cryptographic hash function", then you'll need to define your setting more precisely (what are the inputs? how is $H$ modelled?  how is it represented and provided as input to the algorithm? etc.).



Footnote [*]: I over-simplified a little bit: technically, the attacker could potentially gain up to a $2n$ improvement in success probability by using the fact that $H(\alpha u)$ tells you something about $H(2 \alpha u)$.  But this can be accounted for in the proof by treating each query $w$ to $H$ as providing $2n$ guesses at a good $\alpha$, for free (namely, $w/2^{n-1},\dots,w/2,w,2w,\dots,2^{n-1}w$).  In this way, one can adapt the proof to show that you'll need at least about $d^n/(2n)$ queries to $H$ to have a good chance of finding a valid solution, and that is still $2^{\Omega(n)}$.