Tommy,
in conjunction with your idea of substituting the relative minor for major chords, and vice versa, you could do the same thing here. It would take some experimentation to get backing tracks that work with completely different chords... but you might get some snippets that are worth saving, that probably would not have generated otherwise.