Generating a random path in a grid without deadlock
You have a solid grid graph, and want to generate a random Hamiltonian path in it.  The following paper describes a polynomial-time algorithm to generate such a path, randomly (from a distribution that is close to uniform):

Self-testing algorithms for self-avoiding walks. Dana Randall, Alistair Sinclair. Journal of Mathematical Physics, vol 41 no 3, pp. 1570–1584, 2000.

Be warned that the algorithm is fairly complex.

Here is a more recent paper that also proposes an algorithm to solve this problem:

Secondary Structures in Long Compact Polymers.  Richard Oberdorf, Allison Ferguson, Jesper L. Jacobsen, Jane' Kondev.  arxiv.org:cond-mat/0508094

On cursory inspection, it looks like it might be easier to implement.



Other related work that might possibly be of interest:

The following paper proposes an algorithm to count the number of such Hamiltonian paths:

A matrix method for counting hamiltonian cycles on grid graphs.  Y. H. Harris Kwong, D. G. Rogers.  European Journal of Combinatorics, vol 15 no 3, pp.277-283, 1994.

I found a reference that claims that the following paper describes 

Enumeration of tours in Hamiltonian rectangular lattice graphs.  Basil R. Myers.  Mathematics Magazine, vol 54, no 1, Jan 1981.

Often, if you can count the number of objects of a particular type, you can sample uniformly at random from the set of such objects.  So, that would be a good starting point to look, if you don't like either of the two papers mentioned above.

The following paper describes how to find a Hamiltonian path of such a solid grid graph (but with no guarantees of any particular random distribution on the output): 

Hamiltonian Cycles in Solid Grid Graphs.  Christopher Umans, William Lenhart.  FOCS 1997.

See also https://mathoverflow.net/q/1592/37212, https://stackoverflow.com/q/7371227/781723, Hamiltonian path in grid graph.