Since "it's okay to preprocess the graph for a long time", one can base the cycle sampling on the (exponential-time) enumeration of cycles/paths, e.g., described in my paper Making Walks Count: From Silent Circles to Hamiltonian Cycles.

This way, pick the first edge $(u,v)$ of a cycle randomly based on the proportion of cycles that contain this edge. Then, pick the second edge $(v,w)$ based on the proportion of cycles that contains path $(u,v,w)$ among those that contain edge $(u,v)$, and so on.

Since "it's okay to preprocess the graph for a long time", one can base the cycle sampling on the (exponential-time) enumeration of cycles/paths, e.g., described in my paper Making Walks Count: From Silent Circles to Hamiltonian Cycles.

This way, pick the first edge $(u,v)$ of a cycle randomly based on the proportion of cycles that contain this edge. Then, pick the second edge $(v,w)$ based on the proportion of cycles that contain path $(u,v,w)$ among those that contain edge $(u,v)$, and so on.