The followig auxiliary result is needed to settle this question. Let us consider an $n\times n$ Jordan block
$$
B=\left(\begin{array}{ccccc}
\lambda&1&0&\cdots&0\\
0&\lambda&1&\cdots&0\\
\vdots&\ddots&\ddots&\ddots&\vdots\\
0&\cdots&0&\lambda&1\\
0&\cdots&\cdots&0&\lambda
\end{array}\right).
$$
If $0\le k\le n$, then we see that $(B-\lambda I)^k$ has a diagonal of length $n-k$
filled with $1$s. Therefore its rank is $n-k$, and thus its nullity is equal to $k$. If $k>n$, then the nullity of this block is, of course $n$. We can summarize this by saying that the nullity of $(B-\lambda I)^k$ is $\min\{n,k\}$.
The OP can use this to handle the case $\lambda=3$. Assume that the Jordan blocks
associated to this eigenvalue have size $n_1\ge n_2\ge\cdots\ge n_m$. The characteristic polynomial tells us that $n_1+n_2+\cdots+n_m=6.$ For its part the minimal polynomial tells us that $n_1=3$. We are left with three possibilities:
A) $m=2,n_1=n_2=3$, B) $m=3, n_1=3,n_2=2,n_3=1$, C) $m=4, n_1=3, n_2=n_3=n_4=1$.
Applying the above observation to all those Jordan blocks we see that the nullity of $(A-3\lambda I)^2$ is
$$
\sum_{j=1}^m\min\{n_j,2\},
$$
which adds up to $2+2=4$ in case A, $2+2+1=5$ in case B, and $2+1+1+1=5$ in case C. Thus we are left with case A as the only possibility, and can conclude that the matrix $A$ has two $3\times3$ Jordan blocks beloging to $\lambda=3$.
Let's follow this algorithm described by Stefan Friedl.
A little work shows that the characteristic polynomial of $C$ is
$$
\chi_C(t)
= t \cdot (t - 1)^{3}
$$
which gives a table of eigenvalues
$$
\begin{array}{c|c|c}
\lambda & \operatorname{am}_C(\lambda) & \operatorname{gm}_C(\lambda) \\ \hline
0 & 1 & ? \\
1 & 3 & ?
\end{array}
$$
Here, $\operatorname{am}_C(\lambda)$ is the algebraic multiplicity of $\lambda$ as an eigenvalue of $C$ and $\operatorname{gm}_C(\lambda)$ is the geometric multiplicity.
Our factorization of the characteristic polynomial allowed us to fill in the algebraic multiplicities in our table. The geometric multiplicities can be computed from the definition $\operatorname{gm}_C(\lambda)=\operatorname{nullity}(\lambda\cdot I-C)$. In our case, we have
$$
\begin{array}{c|c|c}
\lambda & \operatorname{am}_C(\lambda) & \operatorname{gm}_C(\lambda) \\ \hline
0 & 1 & 1 \\
1 & 3 & 1
\end{array}
$$
Note that $\operatorname{gm_C}(0)$ can also be quickly inferred from the inequality $1\leq\operatorname{gm}_C(0)\leq\operatorname{am}_C(0)=1$.
At this stage, we can infer the Jordan form $J$ of $C$. Recall the interpretations of the multiplicities of the eigenvalues as
\begin{align*}
\operatorname{am}_C(\lambda) &= \text{number of $\lambda$'s on the diagonal of $J$} \\
\operatorname{gm}_C(\lambda) &= \text{size of the largest Jordan block corresponding to $\lambda$ inside $J$}
\end{align*}
In general, knowing these multiplicities is not enough to infer $J$. However, in our case we can see that
$$
J=\left[\begin{array}{r|rrr}
0 & 0 & 0 & 0 \\
\hline
0 & 1 & 1 & 0 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1
\end{array}\right]
$$
Now, we proceed to compute the change of basis matrix $P$. The easiest way to start is to note that
$$
E_0 = \operatorname{Span}\{\langle1, 0, 0, 0\rangle\}
$$
This gives our first column of $P$, so
$$
P=
\left[\begin{array}{rrrr}
1 & ? & ? & ? \\
0 & ? & ? & ? \\
0 & ? & ? & ? \\
0 & ? & ? & ?
\end{array}\right]
$$
Now, to build the other three columns, we compute the numbers
$$
d_k=\operatorname{nullity}((\lambda\cdot I-C)^k)-\operatorname{nullity}((\lambda\cdot I-C)^{k-1})
$$
for $1\leq k\leq\operatorname{gm}_C(\lambda)$ where $\lambda=1$. For us, these numbers turn out to be
\begin{align*}
d_1 &= 1 & d_2 &= 1 & d_3 &= 1
\end{align*}
We now take these numbers and build a diagram of empty boxes
$$
\begin{array}{c}
\Box\\ \Box\\ \Box
\end{array}
$$
The algorithm we're following demands that we start at the bottom of this diagram and fill the boxes in row $k$ with linearly independent vectors that belong to $\operatorname{Null}((\lambda\cdot I-C)^k)$ but not $\operatorname{Null}((\lambda\cdot I-C)^{k-1})$. Once a box in the diagram is filled with a vector $\vec{v}$, the box immediately above it is filled with $(\lambda\cdot I-C)\vec{v}$.
In our situation, we have
\begin{align*}
(I-C)^2 &= \left[\begin{array}{rrrr}
1 & 0 & 1 & -1 \\
0 & -1 & -1 & 2 \\
0 & -1 & -1 & 2 \\
0 & -1 & -1 & 2
\end{array}\right] & (I-C)^3 &= \left[\begin{array}{rrrr}
1 & 0 & 1 & -1 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0 \\
0 & 0 & 0 & 0
\end{array}\right]
\end{align*}
We easily see that $\langle0,1,0,0\rangle\in\operatorname{Null}((I-C)^3)$ but $\langle0,1,0,0\rangle\notin\operatorname{Null}((I-C)^2)$. This allows us to fill out our diagram
$$
\begin{array}{c}
\fbox{$\left\langle0,\,-1,\,-1,\,-1\right\rangle$}\\
\fbox{$\left\langle-1,\,-1,\,1,\,0\right\rangle$} \\
\fbox{$\left\langle0,\,1,\,0,\,0\right\rangle$}
\end{array}
$$
This defines our matrix $P$ as
$$
P = \left[\begin{array}{rrrr}
1 & 0 & -1 & 0 \\
0 & -1 & -1 & 1 \\
0 & -1 & 1 & 0 \\
0 & -1 & 0 & 0
\end{array}\right]
$$
We can verify ourselves that this is indeed correct
$$
\overset{C}{\left[\begin{array}{rrrr}
0 & -1 & -2 & 3 \\
0 & 0 & -2 & 3 \\
0 & 1 & 1 & -1 \\
0 & 0 & -1 & 2
\end{array}\right]}
=
\overset{P}{\left[\begin{array}{rrrr}
1 & 0 & -1 & 0 \\
0 & -1 & -1 & 1 \\
0 & -1 & 1 & 0 \\
0 & -1 & 0 & 0
\end{array}\right]}
\overset{J}{\left[\begin{array}{r|rrr}
0 & 0 & 0 & 0 \\
\hline
0 & 1 & 1 & 0 \\
0 & 0 & 1 & 1 \\
0 & 0 & 0 & 1
\end{array}\right]}
\overset{P^{-1}}{\left[\begin{array}{rrrr}
1 & 0 & 1 & -1 \\
0 & 0 & 0 & -1 \\
0 & 0 & 1 & -1 \\
0 & 1 & 1 & -2
\end{array}\right]}
$$
Best Answer
Notice at the lower left corner, the entry is non-zero. The minimal polynomial is indeed $x^4$.