A complex polynomial is determined by its zeros and ones.
The fact that the zeros of $P$ and $Q$ are the same means that $P$ and $Q$ are both of the form $(x-z_1)^{p_1}\cdot\ldots\cdot(x-z_n)^{p_n}$, where $p_i$'s for $P$ can be different from the $p_i$'s for $Q$.
The proof that the powers must be equal is done by induction. The result is clearly true when the number of factors is $1$. So fix $P(z)$, let $n$ be the smallest possible number of factors in any polynomial sharing its roots and 1's with $P(z)$, and let $Q(z)$ be a polynomial with that number of factors. If $P(z)\neq Q(z)$, then we can multiply and divide $P(z)$ and $Q(z)$ in a way that would result in a polynomial with a smaller number of factors, which would be a contradiction.
To answer your comment, an example for the number of factors being $2$ is:
If $P(x)=(x-z_1)^{p_1}(x-z_2)^{p_2}$ and $Q(x)=(x-z_1)^{q_1}(x-z_2)^{q_2}$, then WLOG assume $p_1\neq q_1$. Then $P(x)^{q_1}\neq Q(x)^{p_1}$. And dividing them, we see that $R(x)$ := $P(x)^{q_1}/Q(x)^{p_1}$ has the same set of $1$'s as $P(x)$ and $Q(x)$. On the other hand, $R(x)=(x-z_2)^{q_1p_2-p_1q_2}$ (or 1/R(x) if that exponent is negative) is a polynomial consisting of just $1$ factor, contradicting the assumption that $Q(x)$ was the polynomial with the smallest number of factors that had the same roots as $P(x)$.
Your original idea works.
I will prove the following
Lemma: Let $P$ be a non-constant complex polynomial of degree $d$. Let $n$ and $m$ be the number of different zeros of $P$ and $P-1$, respectively. Then we have $n+m\geq d+1$.
The original question follows from the lemma by considering $P-Q$.
Proof of Lemma: Write $P=c\prod_{i=1}^n(x-z_i)^{r_i}$ and $P-1=c\prod_{j=1}^m(x-w_j)^{s_j}$. We have $$\frac{P'}P=\sum_{i=1}^n\frac{r_i}{x-z_i}$$ and similarly $$\frac{P'}{P-1}=\frac{(P-1)'}{P-1}=\sum_{j=1}^m\frac{s_j}{x-w_j}.$$
Taking the difference, we get: $$\frac{P'}{P(P-1)}=\sum_{j=1}^m\frac{s_j}{x-w_j}-\sum_{i=1}^n\frac{r_i}{x-z_i}.$$
Multiplying both sides by $F=\left(\prod_{i=1}^n(x-z_i)\right)\left(\prod_{j=1}^m(x-w_j)\right)$, we see that the right hand side becomes a polynomial $G$. Therefore we have $FP'= P(P-1)G$, which has degree at least $2d$. Since $P'$ has degree $d-1$, it follows that $n+m=\deg F\geq d+1$.