Rotation of $v_1$ around the vector $u$ gives $v_2$.
How do I find the angle of rotation?
For another example, if $v_2=q u_1 q'$, and $q$, a quaternion, has the $u$ vector, what would be the scalar part of the $q$?
Note that $u$ and $v_1$ are not perpendicular.
You are seeking $\cos(\theta/2)$ (from which you could recover $\theta$) where $\theta$ is the angle of rotation. I'm also going to assume $u$ isn't parallel to $v_1$, and without loss of generality let's also normalize $v_1$ and $v_2$ to have length $1$.
To find $\cos(\theta/2)$, we could really use a unit vector $x_1$ in the plane of rotation and its image $x_2$ after the rotation. Then we can compute the unit bisector $x_3=\frac{x_1+x_2}{|x_1+x_2|}$, and then the cosine of the angle between $x_1$ and $x_3$ is the cosine of the angle we want. This can be computed (in principle) as long as $x_1+x_2\neq 0$, and if it is equal to zero, well then you already know that $\theta=\pi$ and $\theta/2=\pi/2$.
Notation: for a quaternion $q_0+q_1i+q_2j+q_3k$, let $PQ(q)=q_1i+q_2j+q_3k$. That is, it hands us back the pure quaternion part of the quaternion. Let's also say $\Re(q_0+q_1i+q_2j+q_3k)=q_0$, that is it hands us back the real part. Now, it's a fact that, when $v$ and $w$ are vectors encoded as quaternions with real part $0$, $PQ(vw)$ is the cross product of $v$ and $w$ encoded as a quaternion, and $-\Re(vw)$ is the dot product of $v$ and $w$.
Now $PQ(uv_1)$ is a unit vector lying in the plane of rotation. The same can be said for $PQ(uv_2)$. Furthermore, $qPQ(uv_1)q'=PQ(uv_2)$, and this makes geometric sense: as $v_1$ moves to $v_2$, $PQ(uv_1)$ moves to $PQ(uv_2)$.
Since the dot product of two unit vectors yields the cosine of the angle between, we should just have to compute the following quantity:
$$ \cos(\theta/2)=-\Re\left (\frac{PQ(uv_1)+PQ(uv_2)}{|PQ(uv_1)+PQ(uv_2)|}PQ(uv_1)\right) $$
(The angle between the bisector and $PQ(uv_1)$ is of course $\theta/2$.)
As Jyrki Lahtonen pointed out in the comments, this strategy is numerically unstable when $x_1+x_2\sim 0$. In that case, we'd probably get less error with the alternative strategy of computing $\theta$ with $\cos(\theta)=-\Re(PQ(uv_1)PQ(uv_2))$. In the "dangerous" region where $\theta\sim \pi$, this reduces the amount of small floats we have to compute, and removes a division by a small float.