Cool question.
Let's try to formalize the general concepts presented in the other two responses thus far. Intuitively, the main idea is that the instantaneous axis of rotation is determined by the rotation that takes the object from its configuration at one instant to its configuration at the next instant as opposed to the rotation that takes it from its initial configuration to its configuration at some later time. Let's try to make this precise.
As you already wrote, for any time $t$ we have the following for the position $\vec x(t)$ of a point in the body at time $t$:
\begin{align}
\vec x(t) = R(t)\vec x(0) \tag{1}
\end{align}
where $R(t)$ is a rotation for each $t$. Now consider the configuration of the object at a neighboring time $t+\epsilon$. How is the position of a point in the body at this later point related to its position at the point $t$? Well, notice that
\begin{align}
\vec x(t+\epsilon)
&= R(t+\epsilon)\vec x(0) \\
&= \Big(R(t) + \dot R(t)\epsilon\Big)\vec x(0) + O(\epsilon^2) \\
&= \Big(I + \epsilon\dot R(t)R(t)^t\Big)\vec x(t) + O(\epsilon^2)
\end{align}
For small $\epsilon$, the order $\epsilon^2$ terms become insignificant, so the transformation that takes $\vec x(t)$ to $\vec x(t+\epsilon)$ is the gadget in big parentheses. Let's give it a name:
\begin{align}
\rho(t, \epsilon) = I+\epsilon\dot R(t)R(r)^t
\end{align}
But what exactly is this guy? Well, our intuition tells us that it should be a rotation with axis $\vec\omega(t)$; in particular, $\vec\omega(t)$ should be an eigenvector of this transformation. To see that this is the case,
I make the following:
Claim. $\rho(t,\epsilon)$ takes precisely the form of a "small" rotation about the axis $\vec\omega(t)$. In particular, $\vec \omega(t)$ is an eigenvector of $\rho(t,\epsilon)$.
Proof. First, recall that omega can be defined as the vector that generates the motion of the points in the body as follows:
\begin{align}
\dot{\vec x}(t) = \vec\omega(t)\times\vec x(t) \tag{2}
\end{align}
But notice, using eq. $(1)$ that
\begin{align}
\dot{\vec x}(t) = \dot R(t) \vec x(0) = \dot R(t)R(t)^t\vec x(t) \tag{3}
\end{align}
Now we notice that the matrix $\dot R(t) R(t)^t$ is antisymmetric since $R(t)$ is an orthogonal matrix for each $t$ (I'll leave this for you to prove. It follows that there exist functions $w_x(t), w_y(t), w_z(t)$ for which
\begin{align}
\dot R(t)R(t)^t = \begin{pmatrix}
0 & -w_z(t) & w_y(t) \\
w_z(t) & 0 & -w_x(t) \\
-w_y(t) & w_x(t) & 0 \\
\end{pmatrix}
\end{align}
Using this expression and comparing $(2)$ and $(3)$, it is not hard to show that $w_x,w_y,x_z$ are precisely the components of the angular velocity $\vec\omega$. Putting this all together, we see that $\rho(t,\epsilon)$ can be written as follows:
\begin{align}
\rho(t,\epsilon) = I + \epsilon\vec\omega(t)\times
\end{align}
where $\vec\omega(t)\times$ is shorthand for the transformation mapping any vector $\vec v$ to $\vec\omega(t)\times v$. Now, it is easy to show that $\vec\omega(t)$ is an eigenvector of $\rho(t,\epsilon)$;
\begin{align}
\rho(t,\epsilon)\vec\omega(t) = (I+\epsilon \vec\omega(t)\times)\omega(t) = \vec\omega(t) + \epsilon\vec\omega(t)\times\vec\omega(t) = \vec\omega(t).
\end{align}
It remains to show that $\rho(t,\epsilon)$ has the form of a "small" rotation about the axis $\vec\omega(t)$. Well, what does such a rotation look like? Well, a general rotation by an angle $\theta$ about an axis defined by a unit vector $\hat n$ can be written as follows (I'll again leave it to you to either show this, or find out why this is true):
\begin{align}
R(\hat n, \theta) = \exp(\theta\hat n\cdot \vec J)
\end{align}
Where $\vec J = (J_x, J_y, J_z)$ is a vector of matrices, the so-called rotation generators, whose components are defined by
\begin{align}
(J_i)_{jk}= -\epsilon_{ijk}
\end{align}
and $\exp$ is the matrix exponential. Notice that to first order in $\theta$, this shows that
\begin{align}
R(\hat n, \theta) = I + \theta\hat n\cdot J_i
\end{align}
But now notice that if we apply this to any vector $\vec v$, then we obtain
\begin{align}
R(\hat n, \theta)\vec v
&= (I+\theta\hat n\cdot \vec J)\vec v \\
&= \vec v + \theta n_i (J_i)_{jk}\vec v_k \hat e_j \\
&= \vec v - \theta n_i\epsilon_{ijk} v_k \hat e_j \\
&= \vec v + \theta \hat n\times \vec v \\
&= (I + \theta\hat n\times )\vec v
\end{align}
We now see by inspection that $\rho(t,\epsilon)$ has precisely the form of the first order approximation to a rotation $R(\hat n, \theta)$ if we simply take $\hat n = \hat \omega(t)$ and $\theta = \epsilon|\vec\omega(t)|$. $\blacksquare$
There's a constructive proof that can be understood intuitively. I assume z is vertical and y is forward/backward. You rotate the object about the z-axis until the top is somewhere on the xz plane i.e. y=0. This makes the top of the object point perpendicular to the y-axis, so you can rotate about the y-axis until it points up. And now you just need to rotate it on the z-axis until forward points in the right direction.
If you want to know what the original rotation was, just take the opposite of each of those steps and put them in reverse order. For example, if you rotated 10°, -30°, 50°, then to get the original rotation from the correct rotation it's just -50°, 30°, -10°.
This sequence of operations can always be done regardless of how an object is oriented. It's not necessarily unique. If up is already pointing up, then it will be on the correct plane no matter how much you rotate about the z-axis. But the point is that there is some rotation about the z-axis that leaves it on the correct plane, which there is.
Edit:
If you want something strictly more mathematical, suppose you have an orthogonal frame of vectors, $x = (x_1,x_2,x_3), y = (y_1,y_2,y_3),$ and $z = (z_1,z_2,z_3)$.
$z$ is the top of the object, so first we rotate it so $z'_2 = 0$. We just rotate it by $\arctan\frac{z_2}{z_1}$, and it ends up pointing at $z' = \left(\pm\sqrt{z_1^2+z_2^2},0,z_3\right)$. And rotate it another $180^\circ$ if that got a negative instead of a positive, so it's $z' = \left(\sqrt{z_1^2+z_2^2},0,z_3\right)$. $\arctan\frac{z_2}{z_1}$ is only really undefined in the case of $z_1=z_2=0$, in which case don't rotate it at all.
Now we rotate on the $y$-axis by $\arctan\frac{\sqrt{z_1^2+z_2^2}}{z_3}$ and we get $z'' = \left(0,0,\sqrt{z_1^2+z_2^2+z_3^2}\right)$ which must be $(0,0,1)$ since it's a unit vector. Again, if it's undefined, we don't need to rotate it.
Since $y \perp z$ and we're only rotating, $y'' \perp z''$.
From there, we know $y''_3 = 0$, so we have $y'' = (y''_1,y''_2,0)$.
Just rotate it on the $z$-axis by $\arctan\frac{y''_1}{y''_2}$ plus an extra $180^\circ$ if it faces the wrong way, and we get $y''' = \left(0,\sqrt{y''^2_1+y''^2_2},0\right)$. And that's just $(0,1,0)$, since it's a unit vector.
In this case $y''_1$ and $y''_2$ can't both be zero, so we don't have to worry about $\arctan$ being undefined at all.
Since we rotated on the $z$-axis, and $z''$ was already on the $z$-axis, $z''' = z''$.
All we have left is $x$. Since $x = y \times z$, and we're only rotating, $x''' = y''' \times z'''$.
$x''' = (0,1,0) \times (0,0,1)$
$x''' = (1,0,0)$
Best Answer
Let $A$ be "a displacement of a rigid body such that a point on the rigid body remains fixed", and let $B$ be "a single rotation about some axis." Let's assume we are in three dimensions.
To prove $A$ and $B$ are equivalent, we have to show that $A$ implies $B$ and $B$ implies $A$.
The matrix proof you are describing shows that $B$ implies $A$. In other words, a general rotation (described by an orthogonal matrix) has an axis on which points are invariant under the rotation.
What's left is to show that $A$ implies $B$. At a physicist level of rigor, I think it's fairly obvious that the only way to move a rigid object with one point fixed, is to rotate the object around an axis passing through that point, so at a physicist level of rigor I would consider that proven. Perhaps Goldstein has a more rigorous justification. One way to justify it would be to formalize the idea that a rigid body has 6 degrees of freedom (3 to give the position of one point, and 3 to define its orientation in space). Fixing a point removes three of the degrees of freedom. You can then use 2 of the remaining degrees of freedom to specify an axis, and 1 to specify an angle of rotation about that axis.