Suppose we know that there exists $x \in A$ such that $\phi(x)$, and we want to prove $\psi$. Then the elimination rule for existential quantifiers allows us to argue as follows:
We know that $\exists x \in A . \phi(x)$, and so we may assume to have $a \in A$ such that $\phi(a)$. [Insert argument using $a$ and the fact that $\phi(a)$ here.] Therefore $\psi$, as required.
There is a technical condition, namely that $a$ must not appear in $\psi$. This is precisely how we always use knowledge that something exists. Many authors use the word "choose", as follows:
We know that $\exists x \in A . \phi(x)$, and so choose $a \in A$ such that $\phi(a)$. [Insert argument using $a$ and the fact that $\phi(a)$ here.] Therefore $\psi$, as required.
This has nothing to do with choice! It is still just elimination of existential quantifiers, but the word "choose" confuses many into thinking we're applying the axiom of choice.
All of the above holds equally well classically and constructively. But people worry about constructive math, as if somehow there existence is more special, so let me address this as well. If we have the assumption $\exists x \in A . \phi(x)$ then we need not "construct" an element $a \in A$ such that $\phi(x)$. The assumption gives us some $a \in A$ such that $\phi(a)$. We do not know which $a$ it gives us, but it gives us one. We are thus allowed to use such an $a \in A$, keeping in mind that all we know about it is $\phi(a)$.
Let us apply this to density. Suppose you know that $U \cup V$ is dense in $A$. The definition of density is: for every $\epsilon > 0$ and $x \in A$ there exists $y \in U \cup V$ such that $d(x,y) < \epsilon$. So, given $x_0 \in A$ and $\epsilon_0 > 0$, we may conclude that there exists $y \in U \cup V$ such that $d(x_0, y) < \epsilon_0$. Therefore, we may say: there is $a \in U \cup V$ such that $d(x_0, a) < \epsilon_0$. There is no need to "construct" $a$. The fact that $a$ is there is precisely the existential assumption!