There are two questions here. The first, from the post, is to explain why algebraic numbers are computable; the second, from the comments, is to explain why the OP's argument does not show that Avogadro's constant is transcendental.
Let me tackle the second one first; it gets at a common confusion about computable numbers. When we say a number is computable, we don't mean that we know an algorithm which enumerates its decimal digits, we merely mean that there is some algorithm which does this. For example, let $x=1$ if the Riemann hypothesis is true and $x=2$ otherwise. Then I have no idea what $x$ is - in particular, I don't know a specific program which computes it - but I do know that it's computable: either the "just output $1$" program or the "just output $2$" program computes it. The fact that I don't know which one does the job, while interesting, is irrelevant.
So think back to what you said about Avogadro's number. All you argued was that we can never know with certainty what program computes it; however, there's no a priori reason that some program couldn't just happen to compute it. So it might be computable, even if we have no way of determining exactly what program does the job - in particular, there's no reason (at the moment) to believe that it is irrational.
By contrast, the proof that $\Omega$ is incomputable really shows that no program can compute $\Omega$, full stop, not just that we'll never be able to prove that a specific one does. In particular, you ask whether we could get around the proof by not assuming that we ever manage to prove what program works, but this won't get you around the proof, since it never assumes we ever prove which one works!
OK, now onto the main question: why are algebraic numbers computable?
Alright, first observation. Suppose $a$ is a zero of some nonconstant polynomial $p(x)$. Because it's nonzero, $p$ has only finitely many zeroes; in particular, I can find a pair of rationals $q_0$ and $q_1$ such that $q_0<a<q_1$ and $a$ is the only zero of $p$ between $q_0$ and $q_1$ inclusive. This gives me a pretty good description of $a$: "The unique zero of $p$ in $[q_0, q_1]$."
This isn't all the way to a computation of $a$ yet, but it should make it plausible that $a$ is going to be computable. Next up is some basic calculus. The intermediate value theorem tells us that there are four possibilities for what $p$ does in the interval $(q_0, q_1)$:
$p(x)<0$ for $x<a$, $p(x)<0$for $x>a$.
$p(x)<0$ for $x<a$, $p(x)>0$for $x>a$.
$p(x)>0$ for $x<a$, $p(x)<0$for $x>a$.
$p(x)>0$ for $x<a$, $p(x)>0$for $x>a$.
(Remember that $a$ is the only zero of $p$ in $(q_0, q_1)$!) Note that cases (3) and (4) are basically the same as (2) and (1), respectively. So I'll just do cases (1) and (2). Finally, for simplicity let's assume $q_0=0$ and $q_1=1$.
Let's first deal with possibility (2) (and by extension, (3)).Let's find the first digit of $a$! We compute $p(0.0), p(0.1), p(0.2), ... , p(0.9), p(1)$ - or rather, we just check to see whether each is positive or negative (exercise: show that we can computably do this!). Going from $0.0$ to $1.0$, at some point we switch from positive to negative - say, $p(0.4)<0$ but $p(0.5)>0$. Then we know that $a\in (0.4, 0.5)$ - and the first digit of $a$ is "$4$"! Now we repeat this trick inside the interval $(0.4, 0.5)$ - we look at $p(0.40), p(0.41), ..., p(0.49), p(0.50)$. Going forward like this, we can compute each of the digits of $a$.
Possibility (3) is identical, but with "positive" and "negative" flipped.
What about possibility (1) (and similarly, (4))? This is a bit trickier - there's no obvious "sign change" to look for. But we have a neat observation . . . if we're in case (1), then $a$ is a zero of $p'(x)$, and (since $p$ is nonconstant and has at least one zero) the polynomial $p'$ is nonconstant! So now we switch from looking at $p$ to looking at $p'$: in terms of $p'$ (and picking new $q_0$ and $q_1$ if necessary), is $a$ in case (1), (2), (3), or (4)? If we land in case (2) or (3), we work as above; otherwise, we go to $p''$! And so on. At some point we have to land in case (2) or (3) (why? HINT: take enough derivatives of a polynomial and you get the zero function ...), and then we argue as above.
So we've concluded that there always is some program computing $a$. Note that we seem to have made a lot of choices:
What do we choose as $q_0, q_1$?
If we go down to $p'$, what do we choose for $q_0', q_1'$ etc.?
How many derivatives do we have to take before we land in case (2) or (3)?
However, the sum total of all the choices we make can be coded by a single natural number (the hardest part of this is showing that a finite sequence of rationals can be effectively represented by a single natural number, but that's not hard), so given that number $\alpha$ we can write a program $\Phi_\alpha$ which computes $a$. And in turn, this means we know that for some $\alpha$, $\Phi_\alpha$ computes $a$ - even if we don't know which $\alpha$ does the job, this means $a$ is computable.
