This isn't a full answer, but an attempt to begin to simplify the expression $f_{m,n} = \sum_{i=0}^{m-1} \sum_{j=0}^{n-1} {{i+j}\choose {i,j}} a^i b^j$, as in the comments and in the partial solution in the starting question.
Note that this, too, is a sequence that satisfies the recurrence relation $f_{m,n} = a f_{m-1,n} + b f_{m,n-1} + c$, and has $f_{m,0} = f_{0,n} = 0$ for any $m, n$.
Consider $f'_{m,n} = f_{m,n} - \frac{c}{1 - a - b}$. Then:
$f'_{m,n} = f_{m,n} - \frac{c}{1-a-b} = a f_{m-1,n} + b f_{m,n-1} + c - \frac{c}{1-a-b}\\ = a f'_{m-1,n} + a \frac{c}{1-a-b} + b' f_{m,n-1} + b \frac{c}{1-a-b} + c - \frac{c}{1-a-b} \\= a f'_{m-1,n} + b' f_{m,n-1} + c - (1-a-b) \frac{c}{1-a-b} = a f'_{m-1,n} + b' f_{m,n-1}$
and $f'_{m,0} = f'_{0,n} = -\frac{c}{1-a-b}$. Let $d = -\frac{c}{1-a-b}$. Then this recurrence relation is the same as the original recurrence relation, but with $c = 0$. We can therefore apply your formula to get:
$f'_{m,n} = d a^m \sum_{j = 0}^n {{m+j-1} \choose j} b^j \\ + d b^n \sum_{i = 0}^m {{n+i-1} \choose i} a^i \\ - d$
So in the end, we come down to finding two sums, both of which take the form $\sum_{i = 0}^{n-1} {{k+i-1} \choose i} a^i$.
This is equivalent to finding $\sum_{i = n}^{\infty} {{k+i-1} \choose i} a^i$ (as $\sum_{i = 0}^{\infty} {{k+i - 1} \choose i} a^i = \frac{1}{(1-a)^k}$) in a form that's closed with respect to both $k$ and $n$. I personally doubt that there is a nice expression for this sum except when starting at a fixed $n$.