It suffices to find an integer polynomial $p(x_1, ... x_n)$ such that $p = 0$ has no rational solutions but has solutions $\bmod p$ for all primes $p$; then $\mathbb{Z}[x_1, ... x_n]/p(x_1, ... x_n)$ is such an algebra.
In fact we can take $p(x) = (x^2 - 2)(x^2 - 3)(x^2 - 6)$. The equation $p(x) \equiv 0 \bmod q$ has solutions modulo $q = 2, 3$ by inspection; for all larger primes, $\left( \frac{2}{q} \right) \left( \frac{3}{q} \right) = \left( \frac{6}{q} \right)$, so one of $2, 3, 6$ must be a quadratic residue $\bmod q$.
Some additional comments.
- $p$ clearly cannot be linear.
- The Hasse principle suggests we should not try to look for examples with $p$ quadratic.
- $p$ cannot be cubic if $n = 1$. This is a consequence of the following more general fact:
Proposition: A monic irreducible integer polynomial in one variable has no roots modulo infinitely many primes $p$.
This is a nice exercise in group theory and Galois theory together with the Frobenius density theorem (nowadays usually subsumed under Chebotarev's density theorem).