How should one simulate self-avoiding random walks?
I'm not sure if I'm interpreting your question correctly, but it sounds to me that you're asking not about simulating self-avoiding random walks, but about enumerating self-avoiding random walks.  I say this because you talk about exponentiating an adjacency matrix, which will give you a (weighted) enumeration of random walks.

I'm not sure if there is much literature on enumerating self-avoiding walks in general graphs; I believe that most attention has been focused on self-avoiding walks in lattices in Euclidean space, and that's what my comments below are based on.  I suspect that many of the ideas will carry over to general graphs.

The classic tool for reducing the labor involved in exactly enumerating self-avoiding walks is the lace expansion.  You should be able to locate the relevant literature easily with that keyword.  For highly connected graphs, though, my guess is that the lace-expansion idea won't help too much (but then maybe nothing will help much in that case).

If you're satisfied with approximate enumeration then there are a few options.  See EJJ van Rensburg's 2009 paper on "Approximate enumeration of self-avoiding walks" for a survey.  See also "Self-testing algorithms for self-avoiding walks" by Randall and Sinclair (2000).