Solution:

We first note that the main diagonal (the squares with row number equal to column number) is a permutation of $1,2, \ldots, n$. This is because each number $i$ ($1 \leq i \leq n$) appears an even number of times off the main diagonal, so must appear an odd number of times on the main diagonal. Thus, we may assume that the main diagonal's values are $1,2, \ldots, n$ in that order. Call any matrix satisfying this condition and the problem conditions good. Let $g(n)$ denote the number of good matrices. It now remains to show that $g(n) \geq \frac{(n-1)!}{\varphi(n)}$.

Now, consider a round-robin tournament with $n$ teams, labeled from $1$ through $n$, with the matches spread over $n$ days such that on day $i$, all teams except team $i$ play exactly one match (so there are $\frac{n-1}{2}$ pairings), and at the end of $n$ days, each pair of teams has played exactly once. We consider two such tournaments distinct if there is some pairing of teams $i, j$ which occurs on different days in the tournaments. We claim that the tournaments are in bijection with the good matrices.

Proof of Claim: Given any good matrix $A$, we construct a tournament by making day $k$ have matches between team $i$ and $j$ for each $i, j$ such that $A_{i, j}=k$, besides $(i, j)=(k, k)$. Every pair will play some day, and since each column and row contains exactly one value of each number, no team will play more than once a day. Furthermore, given two distinct good matrices, there exists a value (off the main diagonal) on which they differ; this value corresponds to the same pair playing on different dates, so the corresponding tournaments must be distinct. For the other direction, take any tournament. Make a matrix $A$ with the main diagonal as $1,2, \ldots, n$, and for each $k$, set $A_{i, j}=k$ for each $i, j$ such that teams $i, j$ play each other on day $k$. This gives a good matrix. Similarly, given any two distinct tournaments, there exists a team pair $i, j$ which play each other on different days; this corresponds to a differing value on the corresponding good matrices.

It now suffices to exhibit $\frac{(n-1)!}{\varphi(n)}$ distinct tournaments. (It may be helpful here to think of the days in the tournament as an unordered collection of sets of pairings, with the order implicitly imposed by the team not present in the set of pairings.) For our construction, consider a regular $n$-gon with center $O$. Label the points as $A_{1}, A_{2}, \ldots, A_{n}$ as an arbitrary permutation (so there are $n!$ possible labelings). The team $k$ will be represented by $A_{k}$. For each $k$, consider the line $A_{k} O$. The remaining $n-1$ vertices can be paired into $\frac{n-1}{2}$ groups which are perpendicular to this line; use these pairings for day $k$. Of course, this doesn't generate $n!$ distinct tournaments—but how many does it make?

Consider any permutation of labels. Starting from an arbitrary point, let the points of the polygon be $A_{\pi(1)}, A_{\pi(2)}, \ldots, A_{\pi(n)}$ in clockwise order. Letting $\pi(0)=\pi(n)$ and $\pi(n+1)=\pi(1)$, we note that $\pi(i-1)$ and $\pi(i+1)$ play each other on day $\pi(i)$. We then see that any other permutation of labels representing the same tournament must have $A_{\pi(i-1)} A_{\pi(i)}=A_{\pi(i)} A_{\pi(i+1)}$ for all $i$. Thus, if $A_{\pi(1)}$ is $k$ vertices clockwise of $A_{\pi(0)}$, then $A_{\pi(2)}$ is $k$ vertices clockwise of $A_{\pi(1)}$, and so on all the way up to $A_{\pi(n-1)}$ being $k$ vertices clockwise of $A_{\pi(n)}$. This is only possible if $k$ is relatively prime to $n$, so there are $\varphi(n)$ choices of $k$. There are $n$ choices of the place to put $A_{\pi(1)}$, giving $n \varphi(n)$ choices of permutations meeting this condition. It is clear that each permutation meeting this condition provides the same tournament, so the $n!$ permutations can be partitioned into equivalence classes of size $n \varphi(n)$ each. Thus, there are $\frac{n!}{n \varphi(n)}$ distinct equivalence classes, and we are done.