I want to covert $R:=R_{X,-\frac{\pi}{4}} = \pmatrix{1 & 0 & 0\\ 0 & \cos{-\frac{\pi}{4}} & -\sin{-\frac{\pi}{4}} \\ 0 & \sin{-\frac{\pi}{4}} & \;\;\;\cos{-\frac{\pi}{4}}}$ to a quaternion.
Knowing axis and angle, there's a simple way to do that: $q=(\cos{\frac{-\frac{\pi}{4}}{2}}, \sin{\frac{-\frac{\pi}{4}}{2}} \cdot \pmatrix{1\\0\\0} ) = \cos{\frac{\pi}{8}} - \sin{\frac{\pi}{8}}i $
But what if we don't?
Determining the angle: $1+2\cos\alpha = trace(R) = 1+2\cos{-\frac{\pi}{4}} \Rightarrow \alpha = \pm \frac{\pi}{4}$
Determining the axis
The eigenvalue is 1 , so an axis exists which satisfies $Rx=x \Leftrightarrow Rx-Ex=0$
$$
\left[
\begin{array}{ccc|c}
0 & 0 & 0 & 0 \\
0 & \cos{(-\frac{\pi}{4})} -1& -\sin{(-\frac{\pi}{4})} & 0 \\
0 & \sin{(-\frac{\pi}{4})} & \cos{(-\frac{\pi}{4})} -1 & 0\\
\end{array}
\right]
$$
the solution is $(1,0,0)*t$ after normalization $(1,0,0)$ or $(-1,0,0)$. Now if you pick the right combinations $(\frac{\pi}{4},(-1,0,0)), (-\frac{\pi}{4},(1,0,0))$ you get the right quaternion. Otherwise you get the conjugate i.e. the wrong direction. Am I forgetting something? How can I be sure to pick the right combination of angle and axis?
As the question has still no answer I present here a little extended to my comment above approach.
Generally using eigenvector of rotation matrix as unit vector for rotation axis is ambiguous as the vector $v$ or $-v$ can be treated as an eigenvector. However we know that rotation axis in 3D is directed and this direction is substantial to the proper interpretation of rotation.
The proper method of calculation the axis is for example to use Rodrigues formula.
Let $R(u,\theta)$ be rotation matrix with the unit axis vector $u=[x,y,z]^T$ and rotation angle $\theta$.
In this situation we have the formula for generating the exact form of this matrix.
$R(u,\theta)=I+\sin(\theta)K+(1-\cos(\theta))K^2$
where skew-symetric matrix $ K= \begin{bmatrix} 0 & -z & y \\ z & 0 &-x \\ -y & x & 0 \end{bmatrix} $.
As the skew-symetric part of rotation matrix is equal $\sin(\theta)K$ and at the same time skew-symmetric part of any matrix $R$ is equal $K=\dfrac{1}{2}(R-R^T)$ we have a simple formula for calculating the unit vector of axis $v= {\dfrac {1}{2\sin(\theta)}}\begin{bmatrix} r_{32}-r_{23} \\ r_{13}-r_{31} \\ r_{21} -r_{12} \end{bmatrix}$ where $r_{ij}$ are appropriate entries of $R$ matrix.
Of course $\sin\theta$ for this formula must be $\ne 0$. It comprises the case $\theta=\pi$ and trivial $\theta=0$.
So the axis can be calculated unambiguously.
The angle of rotation $\theta$ is calculated from the trace - as you have noticed $tr(R)=1+2\cos\theta$ - what can be also obtained from Rodrigues formula (at this time from symmetrical part of rotation matrix).
This leads to two solution as $\cos\theta$ has the same value for $\pm\theta$. However values of $\sin\theta$ are different for $\pm\theta$, so in fact we have two equivalent solutions $R(v,\theta)=R(-v,-\theta)$.
The case for $\theta=\pi$ is a special one as all following rotations are equivalent $R(v,\pi)=R(-v,-\pi)=R(v,-\pi)=R(-v,\pi)$.
In this case it doesn't matter what a method for calculating unit axis vector would be chosen, it can be also calculation of eigenvector for $R$ or direct calculation from full Rodrigues formula (or more precisely from its symmetrical part).