If the divergence of your vector field was really zero everywhere, then it should be the case that the surface integral
$$
\int_V (\vec{\nabla} \cdot \vec{E}) \, dV = \oint_{\partial V} \vec{E} \cdot d\vec{A}
$$
should be zero for any volume (and its bounding surface) I care to name.
So let's try to calculate this for a thick spherical shell centered at the origin, with inner radius $a$ and outer radius $b$. In this case, the boundary of my volume has two parts: an inner boundary at $r = a$, with normal vector $\hat{n} = - \hat{r}$, and an outer boundary at $r = b$, with normal vector $\hat{n} = \hat{r}$. The surface integral of $\vec{E}$ over the boundary is then
$$
\oint_{\partial V} \vec{E} \cdot d\vec{A} = \oint_{r = a} \left( \frac{\hat{r}}{r^3} \right) \cdot (-\hat{r}\, dA) + \oint_{r = b} \left( \frac{\hat{r}}{r^3} \right) \cdot (\hat{r}\, dA) \\= -\oint_{r = a} \left( \frac{1}{a^3} \right) dA + \oint_{r = b} \frac{1}{b^3} dA \\
= - \frac{4 \pi a^2}{a^3} + \frac{4 \pi b^2}{b^3} \\ = 4 \pi \left( \frac{1}{b} - \frac{1}{a} \right) \neq 0.
$$
So as we can see, it cannot be the case that the divergence of the vector field $\vec{E} = \hat{r}/r^3$ is zero, because this integral never vanishes.
It should also be a bit clearer from this argument why the case of of $\vec{E} = \hat{r}/r^2$ is special: in that case, the $r^2$ behavior of the surface area exactly cancels out the $1/r^2$ behavior of the vector field, and so we have
$$
\oint_{\partial V} \vec{E} \cdot d\vec{A} = \oint_{r = a} \left( \frac{\hat{r}}{r^3} \right) \cdot (-\hat{r}\, dA) + \oint_{r = b} \left( \frac{\hat{r}}{r^3} \right) \cdot (\hat{r}\, dA) \\
= - \frac{4 \pi a^2}{a^2} + \frac{4 \pi b^2}{b^2} =0.
$$
The above argument then makes it plausible, at least, that the divergence of this vector field is zero at points other than the origin.