It holds vacuously for $A = \emptyset$: then $\bigcup A = \emptyset$ and the empty function $\emptyset: \emptyset \to \emptyset$ trivially fulfills $f(a) \in A$ for all $a\in A$ -- because it is impossible to find a counterexample in an empty set.

Let $n_0 \in\mathbb{N}$ be the smallest number such that there is $A$ of cardinality $n_0$ with $\emptyset \notin A$, but no choice function $f:A \to \bigcup A$ with $f(a)\in a$ for all $a\in A$. We just saw that $n_0$ cannot be $0$. Also, it cannot be $1$: for if $A = \{a\}$ for some nonempty set $a$, pick $x_0 \in a$ and let $f:A\to \bigcup A = a$ be defined by $a\mapsto x_0 \in a$. 

So we have $n_0 > 1$. Let $a_0\in A$. Because $n_0$ is the smallest integer such that there is no choice function, there *is* a choice function $f:(A\setminus \{a_0\})\to \bigcup(A\setminus\{a_0\})$. Pick $x_0\in a_0$ (which is possible since $a_0\neq \emptyset$). Now set $$f' = f \cup \{(a_0, x_0)\}.$$ It is easy to verify that this is a choice function for $A$, contradicting the assumption that $A$ does not have a choice function.