I'm assuming that your gravity acts on the vertical axis, and that your launch angle is an altitude (measured vertically from the horizon, so 0° means firing horizontally, and 90° means firing straight up). Our turret is still free to pivot on the azimuth (side to side) to track the target and intercept it if it's moving laterally.
The first thing we'll do is take the absolute target position \$\vec p_T\$ and launch position \$\vec p_L\$ construct a relative target position vector \$\vec r\$, and its projection on the horizontal plane \$\vec r_h\$ and vertical axis \$r_v\$:
$$\begin{align}
\vec r &= \vec p_T - \vec p_L\\
r_v &= \vec r \cdot \vec {up}\\
\vec r_h &= \vec r - r_v \vec {up}
\end{align}$$
This lets us take launch position right out of the equation. We can apply the 2nd & 3rd steps to the target's velocity vector \$\vec v\$ to split it into a horizontal vector \$\vec v_h\$ and a vertical component \$v_v\$.
Now if we want to hit the target at an initially unknown time \$t\$ seconds after launch, we'll need to cover the horizontal displacement \$\vec r_h + \vec v_h t\$ in a straight line in time \$t\$. So the horizontal component of our launch velocity \$\vec l_h\$ is:
$$\vec l_h = \frac {\vec r_h + \vec v_h t} t$$
Given our desired launch angle \$ \theta \$, we know the ratio between the horizontal and vertical launch speeds is:
$$\begin{align}
\tan \theta &= \frac {l_v} {\| \vec l_h \|}\\
\tan \theta \cdot \|\vec l_h\| &= l_v\\
\tan^2 \theta \cdot l_h^2 &= l_v^2\\
\tan^2\theta \left( \frac {\vec r_h + \vec v_h t} t \right)^2&= l_v^2\\
\tan^2\theta \left( \frac {r_h^2} {t^2} + 2 \frac {\vec r_h \cdot \vec v_h} t + v_h^2 \right) &= l_v^2
\end{align}$$
Now we want to know if that vertical launch velocity will bring us to our target's height at the end of the arc at time \$t\$:
$$\begin{align}
l_v t - \frac g 2 t^2 &= r_v + v_v t\\
l_v &= \frac {r_v} t + v_v + \frac g 2 t\\
l_v^2 &=
\frac {r_v^2} {t^2} + \frac {2 r_v v_v} t + r_v g + v_v^2 + v_v g t + \frac {g^2} 4 t^2\\
\tan^2\theta \left( \frac {r_h^2} {t^2} + 2 \frac {\vec r_h \cdot \vec v_h} t + v_h^2 \right) &=
\frac {r_v^2} {t^2} + \frac {2 r_v v_v} t + r_v g + v_v^2 + v_v g t + \frac {g^2} 4 t^2\\
\tan^2\theta \left( r_h^2 + 2 \vec r_h \cdot \vec v_h t + v_h^2 t^2 \right) &= r_v^2 + 2 r_v v_v t + r_v g t^2 + v_v^2 t^2 + v_v g t^3 + \frac {g^2} 4 t^4\\
0 &= t^4 \cdot \left(\frac {g^2} 4 \right)\\
&+ t^3 \cdot \left( v_v g \right) \\
&+ t^2 \cdot \left(r_v g + v_v^2 - \left( \tan \theta \right)^2 v_h^2 \right)\\
&+ t \cdot 2 \left(r_v v_v - \left( \tan \theta \right)^2 \vec r_h \cdot \vec v_h \right)\\
&+ r_v^2 - \left( \tan \theta \right)^2 r_h^2\\
\end{align}$$
Now we have a quartic equation in one variable with known real number coefficients. As described in this answer, you can apply your favourite quartic solving routine (there's an example in the comments) to find potential values of \$t\$ that satisfy the equation. In general there could be up to four solutions. We're looking only for those that...
- are real numbers (zero imaginary component)
- are greater than zero (negative values correspond to shots the target could have lobbed at us to strike us at our launch angle at time 0)
- yield a positive vertical launch velocity \$l_v\$. (Since the formula we solved involved only the square of the angle's tangent, we discarded the sign, so we can get some false positives that aim downward instead of upward)
If you have multiple candidate solutions that meet those criteria, you can choose freely between them. Generally the smaller the time value \$t\$ the shallower the arc, but also the less time the target has to change course and dodge. Higher \$t\$ solutions typically correspond to taller arcs (we spend more time flying up and down through the air), giving the target more time to evade.
With your chosen time \$t\$ in hand, you can substitute it into the equations above to find your horizontal & vertical launch velocity components, and combine them into the final velocity.
