Is there a non-decreasing sequence $(a_n)$ such that $\sum 1/a_n=\infty$ and $\sum1/(n+a_n)<\infty$?

We use Abel's (or Pringsheim's) theorem:

If $b_n$ is decreasing and positive, and if $\sum b_n$ converges, then $\lim\limits_{n\rightarrow\infty} nb_n=0$.

Now, if $\sum {1\over n+a_n}$ converged, we would have the string of implications: $${n\over n+a_n}\rightarrow 0\quad \Rightarrow \quad{a_n\over n} \rightarrow\infty \quad\Rightarrow\quad {n\over a_n}\rightarrow0\quad\Rightarrow \quad\sup{n\over a_n}<\infty.$$

A self contained and elementary proof. (See below the cut for the "explanation" invoking Abel's theorem.)

As noted by the OP, it suffice to consider the series $\sum \max(a_j,j)^{-1}$. Let $(n_k)$ and $(m_k)$ be two sequences of increasing positive integers satisfying

$$ 0 < \cdots < n_k < m_k < n_{k+1} < m_{k+1} < \cdots $$

such that when $n_k \leq j < m_k$ we have $a_j \geq j$ and $m_k \leq j < n_{k+1}$ we have $j > a_j$.

This implies that (using monotonicity of $a_j$)

$$ \sum_{j = 1}^\infty \frac{1}{\max(a_j,j)} = \sum_{k = 1}^{\infty} \left( \sum_{j = n_k}^{m_k-1} \frac{1}{a_j} + \sum_{j = m_k}^{n_{k+1} - 1} j^{-1}\right) \geq \sum_k (1-n_k/m_k) + \ln \frac{n_{k+1}}{m_k} $$

But observing that $\ln$ is concave, we have that

$$ \geq - \ln \frac{n_k}{m_k} + \ln \frac{n_{k+1}}{m_k} = \sum \ln n_{k+1} - \ln n_{k} $$

a telescoping sum. Using that $(n_k)$ is strictly increasing and integer valued, we get a contradiction.

Basically this is a modification on Abel's theorem as in David Mitra's answer. If $a_j$ and $j$ interchanges "leads" infinitely often, then $\limsup \frac{n}{n+a_n} \neq 0$, and hence $\frac{1}{n+a_n}$ cannot be convergent. Therefore for that series to converge, there exists some $M < \infty$ such that $a_l > l$ for all $l > M$. This implies than the $(a_l)^{-1}$ must also be a convergent series.