Axiom of Choice (for example in the Snake Lemma) If we have to make a choice, but in the end it doesn't matter what choice we made, did we really make a choice to begin with?
More explicitly, somewhere in the standard diagram-chasing proof of the snake lemma for $R$-modules (see http://mathworld.wolfram.com/SnakeLemma.html) we use the fact we have a surjective map $A \twoheadrightarrow B$ and an element $b \in B$ to deduce that there is some element $a \in A$ which maps to $b \in B$. We use this element $a$ to define a map $\mathrm{Ker}(\gamma) \to \mathrm{Coker}(\alpha)$. It turns out of course, that the map we get is independent of the choice of $a$. 
Are we really using the axiom of choice here since the choice we make is irrelevant? I understand that there are proofs of the Snake Lemma in its various forms that avoid the usage of selecting an element but I am more interested in what happens here.
 A: You are right to be wary: using a "there exists some $a$" in a context where you already have an outer assumption of a general element of infinite set is always sketchy.
Fortunately, there's an easy out here: you haven't actually made a choice! $(b,a)$ are just general elements of the set $\{(b,a) \in B \times A \mid f(a)=b\}$. You don't need the axiom of choice to show that the projection to $B$ is surjective.
It's not until the very end when you have a set of pairs {(b,v) | v is a possible value for the image of b} that you make a choice -- but now for each $b$ you are choosing from a one-element set, and that's no problem! Or to put it differently, this set is already the graph of the function you were looking for.

There's a function-oriented trick that will work here too.
If you're the type that really doesn't want to think about $a$ but instead a function g(b)=preimage of b you have an alternative: you can define g(b)=set of all preimages of b without invoking choice.
But then you have to be careful that $g(b)$ is a set-valued function.
A: The specific case in question was answered, however I wish to add on the general question.
Yes, there is a use of the axiom of choice even if the actual choice is irrelevant. Consider a Vitali set, for example, that is a choice of representatives for $\mathbb{R/Q}$. We wish to show that such set is non-measurable, and the fact it is non-measurable is indeed independent of the choice of representatives. However without the axiom of choice we may not be able to make a choice at all.
A: Suppose that you have a surjective mapping $f:A \to B$. Then to produce a subset $A_0$ of $A$ such that $f$ restricted to $A_0$ is a surjective and injective mapping to $B$ in general requires the Axiom of Choice. But for a fixed $b\in B$, showing that there is an $a\in A$ such that $f(a)=b$ requires nothing.  (We are assuming here that showing that $f$ is surjective did not involve AC.)   
