For what $n \geq 3$ does there exist an $n \times n$ matrix such that:
EDIT: I had a comment about $n = 3$ likely not being possible, but I removed that now after some helpful comments.
Such a matrix (integer version) can be constructed from a magic square, say with entries $1,\dots,n^2$, by adding suitable multiples of all $n\times n$ permutation matrices: e.g. take $N=n^2$ and add all $N^iP_i$, where $P_1, \dots,P_{n!}$ are in any order.
This is such a wasteful construction that the question raised in my comment above might deserve some attention: what are good upper bounds for the common row and column sum of such a matrix?
Consider the general integer version of the problem: given positive integers $n$ and $K$, find an $n \times n$ matrix of positive integers whose row and column sums are $K$, and no set of matrix elements that is not a row or column sums to $K$. In principle, you can find a $K$ for which this is is possible as follows.
Consider producing your matrix $M$ as the sum of $K$ random permutation matrices, each of which is chosen independently and uniformly from the $n!$ possible permutations. If $S$ is any subset of the entries that is not a row or column, let $Y_S = \sum_{(i,j) \in S} M_{ij}$ be the sum of this subset of the entries of $M$. Now the cardinality of the intersection of $S$ with a random permutation matrix is a random variable that is not a.s. $1$. We can then estimate the probability that $Y_S$, which is the sum of $K$ iid random variables with this distribution, is equal to $K$: in general it should decay like $1/\sqrt{K}$ if $|S| = n$ (which makes the mean of the random variable $1$), and more rapidly if $|S| \ne n$. As soon as $K$ is large enough that the expected number of subsets $S$ with $Y_S = K$ is less than $1$, we know that with positive probability all $Y_S \ne K$, and thus a solution with this $K$ is possible.
