Answer: $a_n = 1 + c(n - 1)$ for fixed $c \ge 0$.
It is clear that the above is a solution, so we prove there are no other solutions.
The expression
$$n - \frac{n a_n - m a_m + 2 a_m - 1}{a_n + a_m - 1} = \frac{n(a_m - 1) + (m - 2)a_m + 1}{a_n + a_m - 1}$$
is an integer for all $n, m \ge 1$. Let $c = a_2 - 1 \ge 0$. Taking $m = 2$, we see that $\frac{c n + 1}{a_n + c}$ is a positive integer.
If $c = 0$, we have $a_n = 1$ for all $n \ge 1$. So assume $c \ge 1$ and suppose that $c n + 1$ is a prime. Clearly $a_n + c \ge 2$, therefore $a_n = 1 + c(n - 1)$. Finally,
$$(a_m - 1) - c \frac{n(a_m - 1) + (m - 2)a_m + 1}{c n + a_m - c} = \frac{a_m(a_m - 1 - c(m - 1))}{c n + a_m - c}$$
is an integer for any $m \ge 1$. By Dirichlet's theorem, we may assume that $n$ is sufficiently large, so we must have $a_m = 1 + c(m - 1)$.