It follows $b=ka-1$ and $a^3 - 1 = \ell b = \ell ka - \ell$, hence $a \mid \ell - 1$, so $\ell = ma+1$. This leads to $a^2 - mka + m - k = 0$. Its discriminant is $\Delta = m^2k^2 - 4m + 4k$. If $m<k$, then $(mk)^2 < \Delta < (mk+2)^2$, and $\Delta = (mk+1)^2$ is impossible because of parity. If $m>k$, then $(mk-2)^2 < \Delta < (mk)^2$, and $\Delta = (mk-1)^2$ is impossible because of parity. So $m=k$, and then $(a,b) = (k^2, k^3-1)$, for all positive integers $k>1$. EDIT. Right. Both omissions stemmed from working with all integers $k,\ell, m$ appearing as having to be larger than $1$ (so as to avoid trivial solutions for $a,b$, as requested in the initial statement; but clearly, as seen, in each case there is a subcase ... Thanks.

There are two other classes of solutions that you have not found in your solution: (1) Assume $m<k$. Then $\Delta = (mk)^2 - 4m + 4k < (mk+2)^2 \; \Leftrightarrow \; (m-1)(k+1) > -2,$ hence $\Delta < (mk+2)^2$ iff $m \neq 1$. If $m=0$, then $k=a^2$ and $b = ka - 1 = a^3-1$. So $(a,b) = (s,s^3-1)$, where $s \geq 2$ is an integer, is a solution. (2) Assume $m>k$. Then $\Delta = (mk)^2 - 4m + 4k > (mk-2)^2 \; \Leftrightarrow \; (m+1)(k-1) > 0,$ hence $\Delta < (mk+2)^2$ iff $k \neq 1$. If $k=1$, then $\Delta = (m-2)^2$, hence $a = m-1$ and $b = ka - 1 = a-1 = m-2$. So $(a,b) = (s,s-1)$, where $s \geq 3$ is an integer, is a solution.