The origin is that Ben Elton and Richard Curtis thought it up for that episode. You're allowed to be original.
The form "God's Earth" or "God's [adjective] Earth" (green, wide, and others) originates from the simple fact that the Christian god (normally referred to simply as "God") was creator of and authority over the earth:
The earth is the LORD'S, and the fulness thereof; the world, and they that dwell therein. - Psalm 24:1
So, "God's anything earth" as a phrasing would come directly from this belief, which predates the English language.
Generally referencing something in terms of God or Christ when there is no real reason to do so, is a mild form of swearing that has been found in English since the Angles and Saxons were converted. (Ironically, since it's considered a sin to do so).
Elton & Curtis use clean to contrast against homophobic slurs which would would use metaphors of dirt and filth to insult gay people (the general statement is a homophobic insult).
Edit with hat-tip to rajah9:
And therefore we can be precise as to "how long has it been around", the episode first aired on the 9th of January, 1986 so it has been around twenty-seven years and one week. And since I remember it from that first airing, I now feel old.