I don't know of a combinatorial solution, but I do know a trick...
The number of $n$-step walks starting at $(x,y)$ that don't leave the grid is obviously the total number of $n$-step walks ($4^n$) times the probability $p_n(x,y)$ that a random $n$-step walk started at $(x,y)$ doesn't leave the grid.
What is that probability? Obviously, $p_0(x,y) = \chi(x,y)$, where $\chi(x,y)$ equals $1$ inside the grid and $0$ on the points surrounding it. For higher $n$, we have the recurrence relation $p_{n+1}(x,y) = \chi(x,y) \frac{p_n(x-1,y) + p_n(x+1,y) + p_n(x,y-1) + p_n(x,y+1)}{4}.$
Except for the $\chi(x,y)$ term, this is almost a convolution, and by making use of the fact that the grid is rectangular, we can get rid of the unwanted term by extending $p_0$ suitably beyond the edges of the grid.
Here it turns out to be much more convenient to let the grid extend from $(1,1)$ to $(a-1, b-1)$, so I'm going to adopt that convention, and then define $p_0(x,y) = f(x)g(y)$, where $f(x) = \begin{cases} \phantom{+}0 & \text{if }x = ka, k \in \mathbb Z \\ \phantom{+}1 & \text{if }(2k+0)a < x < (2k+1)a, k \in \mathbb Z \\ -1 & \text{if }(2k+1)a < x < (2k+2)a, k \in \mathbb Z \end{cases}$ $g(y) = \begin{cases} \phantom{+}0 & \text{if }y = kb, k \in \mathbb Z \\ \phantom{+}1 & \text{if }(2k+0)b < y < (2k+1)b, k \in \mathbb Z \\ -1 & \text{if }(2k+1)b < y < (2k+2)b, k \in \mathbb Z.\end{cases}$
It is then not hard to show that, even if we drop the $\chi(x,y)$ term from the recurrence, $p_n(x,y) = 0$ whenever $x$ is divisible by $a$ or $y$ is divisible by $b$. Thus, we can calculate $p_{n+1}$ for $n \ge 0$ via the convolution $p_{n+1} = p_n * K$, i.e. $p_{n+1}(x,y) = \sum_{u,v \in \mathbb Z} p_n(x-u,y-v) K(u,v),$ where the kernel $K$ is given by $K(1,0) = K(0,1) = K(-1,0) = K(0,-1) = \frac 1 4$ and $K(u,v) = 0$ for all other values of $u$ and $v$.
Why would we want to do that? Well, it just happens that convolutions of discrete periodic functions can be efficiently calculated using discrete Fourier transforms. In particular, letting $\tilde p_n$ and $\tilde K$ denote the Fourier transforms of $p_n$ and $K$, we have $\tilde p_n = \tilde p_{n-1} \tilde K = \tilde p_0 \tilde K^n,$ where the multiplication is simply done pointwise.