Relative prime to $0$ This question is more general, but I am going to use a theorem to motivate it.
Suppose I want to prove that there exists a rational $r$ such that $r^3 + r + 1 = 0$. The first step is to assume that there is such an $r$, so $r = \frac{p}{q}$ where $p,q \in \mathbb{Z}$, $q \neq 0$ where $p,q$ are relatively prime.
Here's my question. If this $r$ were $0$ (it's not, and I can rule out it out, but I'm interested in whether I need to actually rule it out for full rigor), that $r = \frac{0}{q}$. But $0 \cdot 0 = 0$ and $0 \cdot q = 0$, so both $p$ and $q$ have a common factor of $0$.
But $\gcd(p,q) = 1$, still, since $1 > 0$, and it doesn't seem to matter if $q$ is negative.
Based on this, my conclusion is that it doesn't actualy matter if $p = 0$ and I don't need to consider this. Is that right? If I wrote "assume $p$ and $q$ have no common factors," that's already a bit ambiguous because they surely have a common factor of $1$, but the more formal "relatively prime" assumption seems ok.
 A: If we replace "$p,q$ are relatively prime" with "$\frac pq$ is in 'lowest term'" would it change how you think of it?
If $q > 1$ then $\frac 0q = \frac 01$ so $\frac 0q$ is not in lowest terms.
If we use the notation of $\gcd$ and "relative prime" though the arguement is the same.
As $0\cdot q = 0$ we have the $q$ is a divisor of $0$ and so $\gcd(0, q) = q$ and if $q > 1$ then $\gcd(0,q) = q$ and therefore

If $q>1$ then $0$ and $q$ are not relatively prime.

But $\gcd(0,1) = 1$ so

$0$ and $1$ are relatively prime.

And we can just continue.
====
But in your analysis you got confused and made a convolution.
You say:

But 0⋅0=0 and 0⋅q=0, so both p and q have a common factor of 0.

Not quite.  we have $0\cdot q =0$. You do not have $0\cdot something = q$.  So $0$ is NOT a factor of $q$.  So $0$ is not a factor of anything except of itself.
What you do have and should have said is because $0\cdot q = 0$ and $1\cdot q = q$ that it is $q$ (and not $0$)  that is a common factor of $0$ and $q$.
In fact every thing is a factor of $0$ so $\gcd(0,anything) = |anything|$.  (Bear in mind $\gcd(a,b) = \gcd(a,-b) = \gcd(-a, b)=\gcd(-a, -b)$ because if anything divides both $a$ and $b$ it also divides $-a$ and $-b$.)
And $0$ and $q$ are relatively prime means $\gcd(0, q) = 1$.  But $\gcd(0, q) = |q|$ so to have $0$ and $q$ relatively prime we must have $q = \pm 1$.
....
oh, I should point out, as Prasun Biswas correct me, that when we define $\gcd(a,b)$ and the "greatest" common divisor, most texts don't necessarily mean "greatest" in magnitude, but "greatest" in divisibility.  We define $a\preceq b$ to mean that $a$ divides $b$ and that is a partial order (not total, not any two elements compare).  Using this order the "greatest" common divisor is the common divisor that all other common divisor divide into.
For the most part the definition are the same as if $a,b$ are both positive $a\preceq b \implies a \le b$. And if $a,b$ are positive integers the largest common divisor in magnitude and the common divisor greatest in divisibility are the same.
But in this case as everything divides $0$, we always have $q\preceq 0$ and $\max_{\preceq} \mathbb Z = 0$ and $0$ is the greater in divisibility than all integers.  So although all $q$ are common divisors of $0$ and $0$, $\gcd(0,0) = 0$.
