It depends on what you think set theory describes. If you think set theory describes some sort of independently existing structure (sets that exist independent of set theory), then of course for that independently existing structure either the axiom of choice holds, or it doesn't.
However a different view is that sets are defined by set theory in the very same sense as group elements are defined by group theory. In group theory, the statement "there exists a group element of which no positive power is the identity" (let's call it the "infinite order hypothesis") is independent from the group axioms. Yet nobody would consider it a problem; it just means there are models of group theory (that is, groups) where the "infinite order hypothesis" is true (such as the additive group of integers), and there are others where the "infinite order hypothesis" is false (such as additive group of the integers modulo 3).
However note that even if you assume there are some "true sets" independent of ZF set theory which set theory is meant to describe, then the independence of AC of the ZF set theory axioms does not violate the law of the excluded middle. It just means they are not sufficient to describe all aspects of those "true sets"; in particular, they do not allow to decide whether all sets admit a choice function.
Note that also the axiom of infinity is independent of the other axioms of set theory; it is consistent to assume that there are only hereditary finite sets (that is, finite sets whose elements are also finite, as are the elements of their elements, and so on). If you think of set theory as describing some "true sets", then you can also ask whether the axiom of infinity holds for then (i.e. whether there actually exist infinite sets). If, however, you view set theory as just describing a class of models, then set theory with infinity is just describing a specific subclass of models (namely those which actually have infinite sets), and then adding the axiom of choice again describes a specific subclass of those models (namely the class of models where all sets have a choice function), not unlike how the theory of abelian groups describes a subclass of the models (groups) that group theory describes (namely the subclass of groups whose group operation is commutative).