I still don't know about the rank, but here's a step that might let you make some progress on it.

Since $\mathbb Z_p^*$ is the multiplicative subgroup of a finite field, it's known to be cyclic, so that there is an $a$ such that $1=a^0,a,a^2,\ldots,a^{p-2}$ exhaust the subgroup ($a^{p-1}$ being 1 again).

Rearrange the rows and columns of the matrix so that the $i$th row of the matrix corresponds to $a^{i-1}$ and the $j$th row of the matrix corresponds to $a^{j-1}$. This is just conjugation of the original matrix by the permutation matrix arising from the permutation $1\to 1$, $2\to a$, $3\to a^2$ etc and so has the same rank. Let this matrix be $B$.

Once you've done this, the matrix $B$ has entries (labelling from 0 to $p-2$ for simplicity) $b_{ij}=a^{i+j}\bmod p$. In particular, $B$ is a
circulant matrix. For any generator, we have $a^{(p-1)/2}=-1\bmod p$, which implies (essentially as noted by Gerry Myerson) that the sum of the first half of each row and the second half of each row is the vector of all $p$'s.
This guarantees (as before) that the rank is at most $1+(p-1)/2=(p+1)/2$.

However, the fact that $B$ is circulant means that its eigenvalues are known and easily expressed in terms of the elements of the first row. Finding the rank amounts to checking for how many $k$'s, the quantity
$$
\sum_{j=0}^{p-2}(a^j\bmod p)\exp\left(\frac{2\pi ijk}{p-1}\right)
$$ is non-zero. Notice that if $k$ is even and non-zero, then the sum vanishes: if you write the row as the sum of the vector whose entries are all $p/2$ and a vector $u$, then the asymmetry mentioned above in $u$ implies that the sum vanishes with $u$, as it does for the constant vector. So the rank of the matrix is $(p+1)/2$ if and only if the sum is non-zero for all odd $k < p$.