Is a well-ordered set always countable?

Every ordinal is well-ordered by $\in$. Ordinals are arbitrarily large. All the axiom of choice adds is that all sets biject with an ordinal, thereby being well-orderable. Even proper classes can be well-orderable; the class of ordinals is well-ordered by $\in$.

To clarify exactly what's going on, your argument shows there is a countably infinite subset of any infinite well-ordered ordinal. The reason it doesn't show any well-ordered set is countable is that there's no reason your process should exhaust the set A. If we consider the set $\mathbb{N}\cup\{\infty\}$, where we add a point larger than any natural, we can check this is still a well-ordered set. But the process you describe will never "count" the point at infinity. Of course this set is still countable, but the idea is instead of adding 1 point we can add uncountably many (a priori it's not clear how to order these points, this is just supposed to show why we can get uncountable ordinals).

I'd like to point out why your intuitive argument is wrong. Your sequence starts with the smallest element of $A$, then moves to the next smallest element of $A$ - the successor of $a_0$. By induction (as per the Peano axioms), this process will eventually reach every natural number if we apply it to $\mathbb N$. By the way, it's typical to write $\omega = \mathbb N$ when referring to it as an ordinal. The thing is, your process being exhaustive would require that every element of $A$ other than the smallest one is a successor of some other element. I'll give you an example of a well ordered set where this does not hold.

As I said, we have $\omega = \mathbb N$. Let's define a new set, called $\omega + 1$, as $\omega \cup \{\infty\}$, where $\infty$ is just some symbol not in $\omega$. We'll keep the ordering on $\omega$ and assert that $\infty$ is strictly bigger than every element of $\omega$. This makes $\omega + 1$ into a well ordered set. Essentially, if a nonempty subset contains $\infty$ then its minimum is either $\infty$ itself or removing $\infty$ does not change the minimum. Now, if you tried to apply this process to $\omega + 1$, you would get $a_0 = 0$, $a_1 = 1$,... , $a_n = n$. However, you would never reach $\infty$ as there is no $n \in \omega$ whose successor is $\infty$.

I'd like to point you to the notion of transfinite induction, however. This is a method that allows you to make inductive arguments on any well ordered set, as you have tried to do. The difference is that you have to account for these $\infty$ esque elements which are not a successor of anything (called limit ordinals). If you can prove a property $P$ holds for all limit ordinals in $A$ and that $P(\alpha) \implies P(succ(\alpha))$ then $P$ holds for all $\alpha$ in $A$.

I'd also like to point out that the more standard notation is $\omega + 1 = \omega \cup \{\omega\}$. This definition of the successor ordinal allows for a very clean theory. Here, we have that $\omega \in \omega + 1$ is a limit ordinal, so doing induction on $\omega + 1$ requires treating this case specially.