Can we build choice function by choosing randomly (and then memorizing the value)? Imagine following set of actions for constructing a choice function f - for an element S we are choosing randomly and element from S, since then we memorize this value so that whenever function is called we always return that element. That said, before we call the function the very first time anything is possible but after we invoked it - there's no way back, in our universe since that moment everybody who calls f(S) will get exactly the same result.
Does this construction equivalent to invoking Axiom of Choice? In other words, does statement "we can always choose a random value from a set" equivalent to just "we can always choose an element from set"?
 A: Despite what it may sometimes seem, mathematics is (classically) concerned with a static and pre-existing universe. We study what is and isn't in that universe. Is there a well-ordering of the reals? Is there a cardinal between the natural numbers and the continuum? Are there any such this and that?
The way we study these questions is by assuming a certain base theory, commonly some variant of $\sf ZF$ or a related theory (often done implicitly, too), and trying to prove something exists or that it cannot exist. On occasion, we show that something is not provable by reducing its existence or inexistence to some axiom that we know is independent of our theory.
For example, if we can show that a statement is equivalent to the Continuum Hypothesis, then we know that just by assuming $\sf ZFC$ we cannot determine the truth value of that statement. It may still be true, but it may also fail.
But going back to our study of mathematics, the universe is static. So choice functions exist or they don't. If they do, fixing a choice function, we no longer have any "randomness" in our choice, it will be predetermined and predecided, and we will have presumed to know everything about it. If we had wanted one of the elements to be chosen to have a certain property, we can simply have prepared, in advance, our family of sets accordingly.
What you are describing, is an attempt to prove the existence of a choice function by "repeated existential instantiation". Recall that existential instantiation is the process by which we start with $\exists x\varphi(x)$, and we add a new constant symbol to our language, $c_\varphi$ with the axiom $\varphi(c_\varphi)$. When you write "Let $x$ be such that ..." you are doing just that.
So, you may want to think, we simply go through our non-empty sets, and since "$A$ is non-empty" is the same as saying $\exists x(x\in A)$, we simply add more and more constant to our language, $c_A$, with the axioms $c_A\in A$.
But proofs are finite by definition, and we may have infinitely many sets to choose from. In fact, we may have "non-standardly finite" collection of sets, which is finite from the internal point of view of the universe we're working with, but not from the point of view of ourselves (this, in a sense, is the reverse of Skolem's paradox). But even if we ignore that "non-standard" case, we still have to contend with the fact that the Axiom of Choice is essentially there to solve a problem of infinitely many choices. So repeating existential instantiation is not going to be possible, as it would result in an infinite proof.
And this is the closest we can get to "choose a random element from a set". Because "random" is a meaningless term without context (usually a probability distribution), and by interpreting it as "arbitrary", we really just get existential instantiation.
Let me add, just to make matters perhaps slightly more confusing, but perhaps slightly more intriguing, that to some extent, what you are suggesting is possible through the technique of forcing. We can approximate a new choice function by "making arbitrary choices as we go along", but the key feature of forcing is that it adds new sets to our mathematical universe. So this choice function that we added does not exist to begin with, and in fact it is quite possible that adding it may cause "damage" (in a technical sense) to the universe, if no other choice function existed before. But that's a whole other story to tell.
