Solution:

It is possible for all positive integers $n \geq 3$. To each pair of integers $\{i, j\}$ with $1 \leq i < j \leq n$ associate a prime number $p_{ij} = p_{ji}$ in such a way that distinct pairs are associated with distinct primes.
Then define, for $1 \leq i \leq n$, $a_{i}$ as the product of all the prime numbers $p_{ij}$ with $i$ fixed and $j$ ranging over all numbers from $1$ to $n$ different from $i$. Then the numbers $a_{i}$ satisfy the required properties. Indeed, the prime number $p_{ij}$ divides only $a_{i}$ and $a_{j}$, and therefore the greatest common divisor of $a_{i}$ and $a_{j}$ is equal to $p_{ij}$, while there is no prime number that divides three of the numbers $a_{1}, \ldots, a_{n}$.

The answer to the second question is $4$. For $n = 4$ one can take the numbers $a_{1} = 2 \cdot 3 \cdot 5$, $a_{2} = 2 \cdot 7 \cdot 11$, $a_{3} = 3 \cdot 7 \cdot 13$, $a_{4} = 5 \cdot 11 \cdot 13$. For $n = 5$, however, it is not possible, and a fortiori it is not possible for $n > 5$. Indeed, if $a_{1}, \ldots, a_{5}$ satisfied the given conditions, then for each pair $\{a_{i}, a_{j}\}$ there would be a prime number $p_{ij}$ dividing both $a_{i}$ and $a_{j}$, and all these prime numbers would have to be distinct. Therefore each number would have to be divisible by at least $4$ distinct prime numbers, and each prime number would have to divide at most two of the numbers $a_{i}$. In particular, the prime number $2$ and the prime number $3$ could each divide at most $2$ of the numbers $a_{i}$, so at least one of the $a_{i}$ would not be divisible by either $2$ or $3$. Such a number, being the product of at least four distinct prime numbers, would have to be greater than or equal to $5 \cdot 7 \cdot 11 \cdot 13 = 5005$, contradicting the hypothesis.