**EDIT** -- This actually doesn't completely work.  For instance, a path 'abc' followed by the path 'cbd' does not give a path from a to d, but rather includes the cycle 'bcb'.  I guess my method only discounts some of the non-paths.
****

As you want to avoid cycles in your path, you should be able to achieve this algorithmically by "zero-ing out" the diagonal of your matrix after each multiplication.  Thus whenever a cycle gets counted in $A^n$, we discount it by changing the diagonal entry to 0, and then all future paths won't use that cycle either.

In particular, if $A$ is the adjacency matrix, define $P_1=A$, and $P_{n+1}=(P_n A)^*$, where I use the * to mean "change all diagonal entries to 0".

Then the matrix $P_n$ gives the number of paths of length $n$ between vertices.