The requirements are equivalent to a set of $n-1$ mutually orthogonal latin squares (MOLS) of size $n$ by $n$, something that is known to exist for prime powers $n$ and conjectured to exist only in that case. A construction of such complete sets of MOLS makes use of finite fields, from which the apparent restriction to prime powers arises naturally as the order of a finite field.
Assume that the symbol set is $\{1,...,n\}$.
A pair of $n$ by $n$ latin squares are said to be mutually orthogonal iff any ordered pair of symbols $(i,j)$ occurs once and only once as entries in the same row and same column respectively of the first and second such latin squares.
The existence of a set of R mutually orthogonal latin squares of order $n$ is known to be equivalent to that of an orthogonal array of degree R+2, strength 2, and index 1 over an alphabet of size $n$. That is, an array of $n^2$ rows and R+2 columns such that any ordered pair of symbols appears exactly once in any given pair of columns.
Given an orthogonal array $M$ with $n^2$ rows and $n+1$ columns corresponding to a complete set of MOLS as above, we can construct matrix $A$ satisfying the problem requirements (1) and (2) as follows. By sorting the rows of $M$ (which does not alter its status as an orthogonal array) we can arrange that the first two columns have entries:
$(1,1),(1,2),...,(1,n),(2,1),(2,2),....,(n,n)$
Furthermore by applying a permutation to the symbol set of each remaining column, another symmetry that does not alter its being an orthogonal array, we can arrange WLOG that the first $n$ rows of $M$ have, after the initial entry 1 in the first column, entries in the second through last column that agree, i.e. $(1,k,...,k)$ for the k'th row, $1 \le k \le n$. We shall hereafter refer only to this "reduced" form of the orthogonal array $M$.
To obtain matrix $A$ we now remove the first column and the first $n$ rows and take the transpose of what remains, so that evidently $A$ consists of $n$ rows and $n(n-1)$ columns.
To see that $A$ satisfies (1), each column is a permutation of the symbol set, it suffices to note that all the entries are distinct. For if there were equality between two entries, this would amount to a duplication of the same equality between two entries of a corresponding row of $M$. However equality of entries in a row of $M$ occurs only in the first $n$ rows, which were removed when forming $A$. Thus (1) is established.
For property (2) of $A$, that now two rows of $A$ repeat the same column pairing, we note that this is directly inherited from the construction from orthogonal array $M$, since the pairs that arise from two rows of $A$ are precisely the $n(n-1)$ unequal pairs that arise from taking the corresponding columns of $M$ after the first $n$ rows, containing the $n$ equal pairs, are removed. So these $n(n-1)$ columns of any two rows of $A$ are necessarily all distinct.
This construction can also be made to work in reverse, so that the availability of $A$ is that such fillings are constructed for prime powers $n$ using finite field techniques linked above, and that apart from these there are no other known solutions (the Prime Power Conjecture being that there are no other solutions).