First let me point out that you are mixing "constructive" and "constructible". There are plenty of non-constructive sets which are constructible. In particular because constructive usually refers to something more akin to the "definable from the usual structure of mathematical objects" and not "there is a set theoretic formula which defines it out of the blue".
The negation of the axiom of choice is as non-constructive as the axiom of choice. Just like the axiom of choice doesn't tell us what the choice function might be, the negation of the axiom of choice doesn't tell us what is the family of sets which does not have a choice function. It could be that the axiom of choice fails, for the first time, in some arbitrarily high von Neumann rank; or it could be that it only fails for very very very large families of sets; or it could be that it fails for particular type of families of sets, while it holds for other.
We can't say. In order to draw practical conclusions from the failure of the axiom of choice we usually have to assume more. For example "there is an infinite Dedekind-finite set of real numbers" is a failure of the axiom of choice which is more specific than just "the axiom of choice fails".
To solve this problem of non-constructivity you don't need to negate the axiom of choice, you need to change the system from a deeper place. Probably the law of excluded middle, which is responsible for us being able to assure that the non-constructive objects exist. This is why most constructive systems reject this law; and there is a theorem that the axiom of choice implies the law of excluded middle.
Within the confines of classical logic, and staying with $\sf ZF$:
You might want to ensure that there are sets which cannot be injected into an ordinal; but you can also require that there are sets which cannot be injected into a power set of an ordinal; and you can continue in this fashion.
So one option is to say the following: For each ordinal $\alpha$, there is a set which cannot be injected into $\mathcal P^\alpha(\eta)$ for any ordinal $\eta$. (Where $\mathcal P^\alpha$ is defined by iterating power sets, and taking union at limits.)
You might want to say, the axiom of choice implies the existence of all sort of crazy sets of real numbers. I'll choose "Every set is Lebesgue measurable", or "Every set has Baire property" or "Every game is determined". These axioms usually bring "order" to the world of non-constructive sets of reals. These are all consistent with $\sf DC$, which means that you can even develop reasonable analysis in those models.
And if the axiom of choice is mainly used for "There are some messed up sets of real numbers", things like the axioms above would essentially say "Every set of reals is well-behaved".
You might want to keep your focus on the real numbers, and say "Screw everything, I'm going nuclear" and require that the real numbers are a countable union of countable sets. This has the benefit of destroying completely the usual ways we define measure and category for sets of reals.
You can even go further than that, and require that for every ordinal $\kappa$, $\mathcal P(\kappa)$ is the countable union of sets of size $\kappa$. This is known as axiom $\sf (K)$, but we don't quite know if it's consistent (relative to very large cardinals, which are necessary to say the least). So you can instead take solace in choose "Every limit ordinal has cofinality $\omega$ which has some messed up consequences as well.
You can decide that you want amorphous sets, since those are "the ultimate counterexample". These are infinite sets that cannot be partitioned into two infinite sets. Strongly amorphous sets have the additional property that any partition is all singletons (except finitely many parts). These sets cannot be linearly ordered, they cannot be mapped onto $\omega$, and their cofinite sets make a complete ultrafilter.
Strongly amorphous sets cannot be endowed with any reasonable structure; but in general it is possible to have amorphous sets which are vector spaces over finite fields. Those spaces have the strange property that every proper subspace is finite.
And there are many other ways to say "I see the axiom of choice as responsible for ...", then the opposite would be "... fails in the most horrible way imaginable!".