A possible example of what you're looking for, though of a somewhat different character from the examples given so far, is [the] "algebraic closure of $\mathbb Q$." Läuchli (Auswahlaxiom in der Algebra, Comment. Math. Helv. 37 (1962), 1–18) showed that ZF does not prove the uniqueness of the algebraic closure of $\mathbb Q$. However, it is very easy to construct an algebraic closure of $\mathbb Q$ in ZF. So in some sense there is provably no way to define "the" algebraic closure of $\mathbb Q$ unless we give ourselves the power of making arbitrary choices, via the axiom of choice. This example is a little peculiar, though, since what the ability to make arbitrary choices is needed for is not to construct an instance of the object, but rather to prove the equivalence of different constructions.

Of a similar flavor is the construction of "the" hyperreals as an ultrapower, which is unique up to isomorphism if you assume the continuum hypothesis.