Let $H$ be the orthocenter of $ABC$, and construct $P'$ using the following claim.

Claim — There is a point $P'$ for which
$$\angle APH + \angle AP'H = \angle BPH + \angle BP'H = \angle CPH + \angle CP'H = 0.$$

Proof. After inversion at $H$, this is equivalent to the fact that $P$'s image has an isogonal conjugate in $ABC$'s image. $\square$

Now, let $X$, $Y$, and $Z$ be the reflections of $P$ over $\overline{AH}$, $\overline{BH}$, and $\overline{CH}$ respectively. Additionally, let $Q'$ be the image of $Q$ under inversion about $(PXYZ)$.

Claim — $ABCP' \sim XYZQ'$.

Proof. Since
$$\angle YXZ = \angle YPZ = \angle (\overline{BH}, \overline{CH}) = -\angle BAC$$
and cyclic variants, triangles $ABC$ and $XYZ$ are similar. Additionally,
$$\angle HQ'X = -\angle HXQ = -\angle HXA = \angle HPA = -\angle HP'A$$
and cyclic variants, so summing in pairs gives $\angle YQ'Z = -\angle BP'C$ and cyclic variants; this implies the similarity. $\square$

Claim — $Q'$ lies on the Euler line of triangle $XYZ$.

Proof. Let $O$ be the circumcenter of $ABC$ so that $ABCOP' \sim XYZHQ'$. Then $\angle HP'A = -\angle HQ'X = \angle OP'A$, so $P'$ lies on $\overline{OH}$. By the similarity, $Q'$ must lie on the Euler line of $XYZ$. $\square$

To finish the problem, let $G_1$ be the centroid of $ABC$ and $G_2$ be the centroid of $XYZ$. Then with signed areas,
$$\begin{aligned} [G_1HP] + [G_1HQ] &= \frac{[AHP] + [BHP] + [CHP]}{3} + \frac{[AHQ] + [BHQ] + [CHQ]}{3} \\ &= \frac{[AHQ] - [AHX] + [BHQ] - [BHY] + [CHQ] - [CHZ]}{3} \\ &= \frac{[HQX] + [HQY] + [HQZ]}{3} \\ &= [QG_2H] \\ &= 0 \end{aligned}$$

where the last line follows from the last claim. Therefore $\overline{G_1H}$ bisects $\overline{PQ}$, as desired.

Remark. This solution characterizes the set of all points $P$ for which such a point $Q$ exists. It is the image of the Euler line under the mapping described in the first claim.

Let $(ABC)$ be the unit circle in the complex plane, and let $A = a$, $B = b$, $C = c$ such that $|a| = |b| = |c| = 1$. Let $P = p$ and $Q = q$, and $O = 0$ and $H = h = a + b + c$ be the circumcenter and orthocenter of $ABC$ respectively.

The first step is to translate the given geometric conditions into a single usable equation:

Claim — We have the equation
$$(p+q) \sum_{\text{cyc}} a^3(b^2-c^2) = (\bar{p}+\bar{q})abc \sum_{\text{cyc}} (bc(b^2-c^2)). \quad (1)$$

Proof. The condition that the altitude $\overline{AH}$ bisects $\angle PAQ$ is equivalent to
$$\begin{aligned} \frac{(p-a)(q-a)}{(h-a)^2} &= \frac{(p-a)(q-a)}{(b+c)^2} \in \mathbb{R} \\ \implies \frac{(p-a)(q-a)}{(b+c)^2} &= \overline{\left(\frac{(p-a)(q-a)}{(b+c)^2}\right)} = \frac{(a\bar{p}-1)(a\bar{q}-1)b^2c^2}{(b+c)^2a^2} \\ \implies a^2(p-a)(q-a) &= b^2c^2(a\bar{p}-1)(a\bar{q}-1) \\ \implies a^2pq - a^2b^2c^2\overline{p\bar{q}} + (a^4 - b^2c^2) &= a^3(p+q) - ab^2c^2(\bar{p}+\bar{q}). \end{aligned}$$

Writing the symmetric conditions that $\overline{BH}$ and $\overline{CH}$ bisect $\angle PBQ$ and $\angle PCQ$ gives three equations:
$$\begin{aligned} a^2pq - a^2b^2c^2\overline{p\bar{q}} + (a^4 - b^2c^2) &= a^3(p+q) - ab^2c^2(\bar{p}+\bar{q}) \\ b^2pq - a^2b^2c^2\overline{p\bar{q}} + (b^4 - c^2a^2) &= b^3(p+q) - bc^2a^2(\bar{p}+\bar{q}) \\ c^2pq - a^2b^2c^2\overline{pq} + (c^4 - a^2b^2) &= c^3(p+q) - ca^2b^2(\overline{p} + \overline{q}). \end{aligned}$$

Now, sum $(b^2 - c^2)$ times the first equation, $(c^2 - a^2)$ times the second equation, and $(a^2 - b^2)$ times the third equation. On the left side, the coefficients of $pq$ and $\overline{pq}$ are 0. Additionally, the coefficient of 1 (the parenthesized terms on the left sides of each equation) sum to 0, since
$$\sum_{\text{cyc}} (a^4 - b^2c^2)(b^2 - c^2) = \sum_{\text{cyc}} (a^4b^2 - b^4c^2 - a^4c^2 + c^4b^2).$$
This gives (1) as desired.

We can then factor (1):

Claim — The left-hand side of (1) factors as
$$-(p+q)(a-b)(b-c)(c-a)(ab+bc+ca)$$
while the right-hand side factors as
$$-(\bar{p} + \bar{q})(a - b)(b - c)(c - a)(a + b + c).$$

Proof. This can of course be verified by direct expansion, but here is a slightly more economic indirect proof.
Consider the cyclic sum on the left as a polynomial in $a$, $b$, and $c$. If $a = b$, then it simplifies as $a^3(a^2 - c^2) + a^3(c^2 - a^2) + c^3(a^2 - a^2) = 0$, so $a - b$ divides this polynomial. Similarly, $a - c$ and $b - c$ divide it, so it can be written as $f(a, b, c)(a - b)(b - c)(c - a)$ for some symmetric quadratic polynomial $f$, and thus it is some linear combination of $a^2 + b^2 + c^2$ and $ab + bc + ca$. When $a = 0$, the whole expression is $b^2c^2(b - c)$, so $f(0, b, c) = -bc$, which implies that $f(a, b, c) = -(ab + bc + ca)$.
Similarly, consider the cyclic sum on the right as a polynomial in $a$, $b$, and $c$. If $a = b$, then it simplifies as $ac(a^2 - c^2) + ca(c^2 - a^2) + a^2(a^2 - a^2) = 0$, so $a - b$ divides this polynomial. Similarly, $a - c$ and $b - c$ divide it, so it can be written as $g(a, b, c)(a - b)(b - c)(c - a)$ where $g$ is a symmetric linear polynomial; hence, it is a scalar multiple of $a+b+c$. When $a = 0$, the whole expression is $bc(b^2 - c^2)$, so $g(0, b, c) = -b-c$, which implies that $g(a, b, c) = -(a + b + c)$. $\square$

Since $A$, $B$, and $C$ are distinct, we may divide by $(a-b)(b-c)(c-a)$ to obtain
$$(p+q)(ab+bc+ca) = (\bar{p}+\bar{q})abc(a+b+c) \implies (p+q)\bar{h} = (\bar{p}+\bar{q})h.$$

This implies that $\frac{p+q}{h-0}$ is real, so the midpoint of $\overline{PQ}$ lies on line $\overline{OH}$.

We use complex numbers as in the previous solution. The angle conditions imply that $\frac{(a-p)(a-q)}{(b-c)^2}$, $\frac{(b-p)(b-q)}{(c-a)^2}$, and $\frac{(c-p)(c-q)}{(a-b)^2}$ are real numbers. Take a linear combination of these with real coefficients $X$, $Y$, and $Z$ to be determined; after expansion, we obtain
$$\left[ \frac{X}{(b-c)^2} + \frac{Y}{(c-a)^2} + \frac{Z}{(a-b)^2} \right] pq - \left[ \frac{aX}{(b-c)^2} + \frac{bY}{(c-a)^2} + \frac{cZ}{(a-b)^2} \right] (p+q)$$
$$+ \left[ \frac{a^2 X}{(b-c)^2} + \frac{b^2 Y}{(c-a)^2} + \frac{c^2 Z}{(a-b)^2} \right]$$
which is a real number. To get something about the midpoint of $PQ$, the $pq$ coefficient should be zero, which motivates the following lemma.

Lemma
There exist real $X$, $Y$, $Z$ for which
$$\frac{X}{(b-c)^2} + \frac{Y}{(c-a)^2} + \frac{Z}{(a-b)^2} = 0 \text{ and}$$
$$\frac{aX}{(b-c)^2} + \frac{bY}{(c-a)^2} + \frac{cZ}{(a-b)^2} \neq 0.$$

Proof. Since $\mathbb{C}$ is a 2-dimensional vector space over $\mathbb{R}$, there exist real $X$, $Y$, $Z$ such that $(X, Y, Z) \neq (0, 0, 0)$ and the first condition holds. Suppose for the sake of contradiction that $\frac{aX}{(b-c)^2} + \frac{bY}{(c-a)^2} + \frac{cZ}{(a-b)^2} = 0$. Then
$$\begin{align*} & \frac{(b-a)Y}{(c-a)^2} + \frac{(c-a)Z}{(a-b)^2} \\ &= \frac{aX}{(b-c)^2} + \frac{bY}{(c-a)^2} + \frac{cZ}{(a-b)^2} - a \left( \frac{X}{(b-c)^2} + \frac{Y}{(c-a)^2} + \frac{Z}{(a-b)^2} \right) \\ &= 0. \end{align*}$$
We can easily check that $(Y, Z) = (0, 0)$ is impossible, therefore $\frac{(b-a)^3}{(c-a)^3} = -\frac{Z}{Y}$ is real. This means $\angle BAC = 60^\circ$ or $120^\circ$. By symmetry, the same is true of $\angle CBA$ and $\angle ACB$. This is impossible because $ABC$ is scalene. $\square$

With the choice of $X$, $Y$, $Z$ as in the lemma, there exist complex numbers $\alpha$ and $\beta$, depending only on $a$, $b$, and $c$, such that $\alpha \neq 0$ and $\alpha(p+q) + \beta$ is real. Therefore the midpoint of $PQ$, which corresponds to $\frac{p+q}{2}$, lies on a fixed line. It remains to show that this line is the Euler line. First, choose $P = Q$ to be the orthocenter to show that the orthocenter lies on the line. Secondly, choose $P$ and $Q$ to be the foci of the Steiner circumellipse to show that the centroid lies on the line. (By some ellipse properties, the external angle bisector of $\angle PAQ$ is the tangent to the circumellipse at $A$, which is the line through $A$ parallel to $BC$. Therefore these points are valid.) Therefore the fixed line of the midpoint is the Euler line.

Remark. This solution does not require fixing the origin of the complex plane or setting $(ABC)$ to be the unit circle.