I have $$A = \begin{pmatrix} 0 & \cdots & 0& -a_{0} \\ 1 & \cdots & 0 & -a_{1}\\ \vdots &\ddots & \vdots &\vdots \\ 0 &\cdots & 1 & -a_{n-1} \end{pmatrix} \in M_{n}$$ and, as the title says, I want to know the minimal polynomial, but without using Cayley-Hamilton (as I'm trying to do an alternative, inductive proof of the theorem).
I know that $$m_{e_1} = x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$$
Maybe I can compute $m_{e_i}$ for the other canonical vectors, but it's ugly, and I'm searching for a faster, non-horrible way. Could someone help me?
You have checked that $P=x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$ is the minimal degree monic polynomial such that $P[A](e_1)=0$, so you just need to show that $P[A](e_i)=0$ for every $i>1$ as well.
Now no doubt you noticed during your calculation that $e_i=A^{i-1}(e_1)$. Then $$P[A](e_i)=P[A](A^{i-1}(e_1)) = A^{i-1}(P[A](e_1))=A^{i-1}(0)=0, $$ because polynomials in $A$ commute with each other, and you are done.
In general, if some polynomial in $A$ kills a vector (here $v=e_1$), then it also kills its repeated images by$~A$, and their span. Stated differently, the kernel of the polynomial in $A$ is an $A$-stable subspace.