I strongly doubt that there exists a non-trivial bijection between self-avoiding walks on Z^d and other combinatorial objects. I don't have any intuition as to whether the generating function may have some other number theoretic interpretation, but I haven't seen or heard anything in this regard.
SAWs are sufficiently complicated that it seems almost certain that the generating function for SAWs even on the square lattice them is non-holonomic (see e.g. Andrew Rechnitzer discussing the related model of self-avoiding polygons, "Haruspicy 2: The anisotropic generating function of self-avoiding polygons is not D-finite", link), and the model is unlikely to be "solvable" in the conventional sense.
FYI, Iwan Jensen has enumerated SAWs on Z^2 to 71 steps here, and higher dimensional enumerations due to Gordon Slade, Richard Liang and I are available here.
It's possible for $a_n=n$ and probably most stepsizes without modular or growth obstructions.
We have covered some subset of an mxm square, are situated at the boundary, and want to visit a cell (x,y) in our square. Choose one of the x,y axes and move far away along it, (but not upon it), until stepsize s>>m and distance is some d from the axis. Then take either 1,2, or 4 more steps along the axis. Then alternately move away, and towards the axis, 2*d steps, until we land on it. Then by moving away and towards (x,y), n times, we can reach every point of the form j-1-3n on the axis, by just moving one more step towards (x,y) where j is our current coordinate, which we could shift to anything modulo 3 when we chose one of the 1,2,4 steps. And if 3n-n>m, we dont use any other squares within the the mxm square, to visit (x,y), and emerge on the opposit side. And since s>>m, if we take one more step we are at a boundary of a new square.
WLOG suppose we are at $(0,0)$, with stepsize $s(0)$, and want to visit $(x,y)$, $0\leq x\leq m$, $0\leq y \leq m$, The full path we take consist of these moves. We move south for $k$ squares (or $j(k)$ steps), then alternate west,east, $x$ times, now we are at $(x,-k)$ with stepsize $s(j(k)+2x)$. Then we alternate south, east, $n$ times, now we are at $(x,n-k)$ with stepsize $s(j(k)+2x+2n)$, select $n$ and $k$ such that $y=s(j(k)+2x+2n)+n-k$ and $s(j(k)+2x+2n)>m$. Then take two steps north, we are now at $(x,y+s(j(k)+2x+2n)+1)$. Move 1 step east, you are now at a corner of a square bounding all visited squares, define the new m to be the side of this new square, let (0,0) your position, pick a new point (x,y) and repeat.
PS. I asked a question about the less trivial 1-D version here:
https://math.stackexchange.com/questions/111377/self-avoiding-walk-on-mathbbz
Best Answer
The following paper by Umans and Lenhart gives a polynomial-time algorithm for finding a Hamiltonian cycle in "solid" grid graphs (grid graphs with no holes with area larger than $1$): http://users.cms.caltech.edu/~umans/papers/LU97.ps
For general grid graphs, the problem is NP-complete.
Even though they search for cycles and not paths, the algorithm might be useful, since a complement of a path in a grid is either disconnected (which is easy to detect) or has at most one large hole.