Proving that there does not exist an infinite descending sequence of naturals using minimal counterexample
I would have done it by induction on sequences whose first term $a_0\le n$ instead and the property that they are stationnary from a certain point.
$n=0$ only one sequence, the null sequence, it is stationnary.
For $a_0\le n+1$ then if $a_0\le n$ then we apply induction hypothesis, else since $a_1<a_0$ then $a_1\le n$ and we apply induction hypothesis on the truncated sequence.
Historical note :
Yet we can wonder if the induction principle itself doesn't use the infinite descent to be proved ? In fact Frege demonstrated that it is a consequence of second order logic given the definition of the zero, of a number and the successor operation as defined by Peano.
I found this in this article $§6.4$ (though in french, sorry) : le raisonnement par recurrence, quel fondement ?.
So in the above proof the whole thing holds effectively on these things :
the definiton of $0$ is used when we say that if $a_0\le0$ then the whole sequence is the null-sequence. (i.e. there is no natural <0).
the well ordering of $\mathbb N$ is used when we say that $(a_0\le n+1)\land (a_1<a_0)\Rightarrow a_1\le n+1-1=n$, making full use of the successor definition.
In your proof if we want to be scrupulous, when you say finitely many natural deleted, then it is a bit annoying, because you are biting your tail : you want to proove there are no infinite descending sequence of naturals but you invoque an argument of finitness...
Addendum : (from comments)
In all these proofs which are very close to axiomatic material, we should in theory check everything we write to avoid the biting one's tail issue (i.e. using a result proved by mean of the theorem we want to prove).
Yet here, we can set the starting point as Peano axioms and the induction principle and prove that infinite descent as well as well-ordering principle (i.e. every set of naturals has a minimum) are sound. And in fact these can eventually become new forms of induction on their own.
This are indeed principles used in the other contributors' proofs.
This amounts to showing that the set $M = \{ m \in \mathbb{N} : m \leq a_{0}\}$, where $a_{0}$ is the first member from any sequence in infinite descent, is finite. $ \def\nn{\mathbb{N}} $
This first line of your 'proof' is invalid. You are using merely your intuition to claim that the non-existence of an infinite descending chain of natural numbers follows from the finiteness of some set that you specified. This is circular in this case; proving the equivalence amounts to proving something of roughly the same strength as the original desired theorem.
Instead what you actually need is:
Let $S = \{ n : n \in \nn \land \text{there is a strictly decreasing sequence from $\nn$ starting with $n$ } \}$.
If $S$ is non-empty then let $m = \min(S)$ and (use your other ideas) to prove that there is a strictly decreasing sequence from $\nn$ starting with something less than $m$, which contradicts the definition of $m$.
Therefore $S$ is empty and you are done.
Your proof looks good to me. As @user21820 and others point out, it actually isn't, and the other answers do a better job of explaining this. In fact, even the proof below is inaccurate as the $\dotsb$ implies induction but I haven't stated that, because it's more of an 'intuition' proof. Assuming induction and 'common-sense' properties of natural numbers is not a trivial thing for a very axiomatic question like this. (Thanks @user21820!)
Here's another I thought of: since the $a$s are natural numbers, $a_{n + 1} < a_n$ is equivalent to $a_{n + 1} \leq a_n - 1$ because there are no natural numbers between $a_n$ and $a_n - 1$. Then, let $n = a_1$ and you have $$a_{n+1} \leq a_{n} - 1 \leq a_{n-1} - 2 \leq \dotsb \leq a_1 - n = 0$$ but $a_{n+1} \geq 0$ as it is a natural number, so $a_{n+1} = 0$. Beyond that there can be no smaller numbers.
(I use 'natural' to mean 'positive integer' but it works for 'non-negative integer' or even 'set of integers with a lower bound'.)