Suppose there is a well-known theorem whose usual proof uses Axiom of Choice. Is trying to prove it without Axiom of Choice useless? What merits can such a proof have?
It is often not useless at all. First let me give out a few reasons why it is useful:
On the other hand, it is somewhat useless to try and prove a theorem without the axiom of choice if other parts of the theory already assume it. If you already assume that every vector space has a basis, showing that a certain proposition relying on this property holds without the axiom of choice is moot.
One example for this is the ultrafilter theorem which, together with the Krein-Milman theorem, imply the axiom of choice , so if you end up using both these propositions there is no use in avoiding choice anymore. It's there.
Regardless of the above, one should remember that not all things in modern mathematics are true in the absence of choice (that is, aside from the axiom of choice itself) and often reformulation and distinction between equivalent definitions is required. In those cases one can, and should, ask themselves how much choice is needed for a particular result.
For example, the assertion "$\mathbb R$ is not a countable union of countable sets" requires the axiom of choice, but it is provable from a vastly weaker statement, "countable unions of countable sets are countable".