There are so many questions about rotations of vectors already on this site,
I was surprised when I failed to find one that is really asking just the same exact question.
There are some questions and answers that assume you already have a vector parallel to the desired axis of rotation. And you will get such a vector if you compute the cross product $v_1 \times v_2$, but I will show an alternative method that does not require a known rotation axis and works in any number of dimensions, not just 3D.
The trick is to express $v_2$ as a sum of two orthogonal unit vectors $e_1$ and $e_2$ in the same plane as $v_1$ and $v_2.$
While $v_1$ and $v_2$ are a basis for the vector subspace (the plane) within which you want to rotate $v_1,$
the vectors $e_1$ and $e_2$ are an orthonormal basis for that plane.
We will construct this orthonormal basis so that $e_1$ points in the same direction as $v_1.$
Finding these vectors will mean that we would be able to write
$$ v_2 = c_1 e_1 + c_2 e_2 $$
where $c_1$ and $c_2$ are some scalar values.
It will be convenient to choose the orthonormal basis in such a way that $c_2$ is positive.
First we set $e_1$ to the unit vector in the same direction as $v_1$:
$$ e_1 = \frac{1}{\lVert v_1\rVert} v_1. $$
Now it's simple to find $c_1$ using the dot product:
$$ c_1 = v_2 \cdot e_1. $$
Let $u_2 = c_2 e_2$; then
$$ u_2 = c_2 e_2 = v_2 - c_1 e_1 = v_2 - (v_2 \cdot e_1) e_1. $$
Set $c_2$ to the length of $u_2$, that is, $ c_2 = \lVert u_2\rVert$;
this guarantees that $c_2$ is positive.
Then
$$ e_2 = \frac{1}{c_2} u_2 = \frac{1}{\lVert u_2\rVert}u_2. $$
This is essentially just the Gram-Schmidt process applied to the basis $v_1, v_2.$
Having done all this, it turns out that
\begin{align}
c_1 &= \lVert v_2\rVert \cos \theta,\\
c_2 &= \lVert v_2\rVert\sin \theta,
\end{align}
that is,
$$ v_2 = (\lVert v_2\rVert\cos\theta) e_1 + (\lVert v_2\rVert\sin\theta) e_2. $$
To rotate $v_1$ through an angle of exactly $\theta$ so that it points in exactly the same direction as $v_2$, compute
$$ (\lVert v_1\rVert\cos\theta) e_1 + (\lVert v_1\rVert\sin\theta) e_2. $$
That's a vector just like $v_2$ except that its length is $\lVert v_1\rVert$
instead of $\lVert v_2\rVert$ -- just compare the formulas.
To rotate $v_1$ toward $v_2$ by some other angle $\phi$, just compute
$$ \mathop{\mathrm{rot}_\phi} v_1
= (\lVert v_1\rVert\cos\phi) e_1 + (\lVert v_1\rVert\sin\phi) e_2. $$
Be careful when doing these operations that you are really working with 3D vectors in the usual mathematical sense; they represent only a direction and length, not specific starting and ending points.
I add this warning to the answer because the first diagram illustrating the problem appears to show a basis or set of axes for your 3D coordinates,
while the vectors are drawn as if they originated from a point other than the origin of the coordinates.
Since the vectors in 3D space should be completely described by just three coordinates, it should be possible to simplify the figure by placing the intersection of the axes, the tails of vectors $v_1$ and $v_2,$ and the center of the circle all at the exact same point.
If the reason for drawing the figure as you did is because you are actually trying to find coordinates along a circle in 3D space with a center that is not at the origin, you'll want to find a vector $v_c$ from the origin to the center of the circle and then add $v_1'$ (the rotated $v_1$) to the vector $v_c$. The coordinates of $v_c + v_1'$ will be coordinates of a point on the circle.
I don’t have any disagreement or suggestions on your solution, but I wanted to point out that (consistent with your solution), the answers and comments that say the lines remain perpendicular are wrong for the question you asked, which involves rotating two lines independently out of the same plane that contains them before rotation. (This is not the same as rotating one line out of $P$ and then rotating the other line out of a plane that is not $P$.)
Suppose $\ell$ and $m$ are the $x$- and $y$-axes of standard three-dimensional space. Then the plane $P$ is the $xy$-plane.
If you rotate the $x$-axis out of $P$ (the $xy$-plane) by $90^\circ$, it becomes coincident with the $z$-axis. If you rotate the $y$-axis out of $P$ (the $xy$-plane) by $90^\circ$, it also becomes coincident with the $z$-axis.
The $x$ and $y$ axes are perpendicular, but after each is rotated $90^\circ$ out of the $xy$-plane, they become coincident and the angle between them is zero.
Best Answer
Without loss of generality let $P$ be the $xy$-plane and all vectors be of unit length. The angle between $\bf v$ and $P$ is $\pi-\theta_0$. Now fix $\mathbf v=(\cos\theta_0,0,\sin\theta_0)$ and $\mathbf w(0)=(1,0,0)$, so $\mathbf w(\phi)=(\cos\phi,\sin\phi,0)$.
The angle between $\bf v$ and $\mathbf w(\phi)$ is, by construction, the arccosine of their dot product: $$\cos A(\phi)=(\cos\theta_0,0,\sin\theta_0)\cdot(\cos\phi,\sin\phi,0)=\cos\theta_0\cos\phi$$ $$A(\phi)=\cos^{-1}(\cos\theta_0\cos\phi)$$