Do all categories have a skeleton? Do all categories have a skeleton?
If the category is small and I assume the axiom of choice, I can choose an element of each morphism class and build the skeleton. However, if the category is not small, I don't know whether its skeleton exists.
Moreover: Is it possible that, if the category is not small and does not have any skeleton as subcategory, the category has a skeleton?
 A: The situation with taking skeletons of categories is exactly the same as the situation with taking choice functions on sets; nothing changes. Whatever your metatheoretical presumptions about Choice on discrete sets/classes, the result will be the same so far as the ability to take skeletons of categories goes.
As you've already noted, Choice lets you choose skeletons. Let us observe that conversely, the ability to choose skeletons entails Choice.
Choice says (in one formulation) that given any equivalence relation E on a collection S, we can choose a subcollection of S containing precisely one element from each equivalence class. If we consider the category C whose objects are S, with a unique map between two objects if they are related by E and otherwise no maps between them, then a skeleton for C is precisely the same thing as a choice of representatives from each equivalence class of E.
(Note that this C is indeed a category because E is reflexive and transitive. The composition structure of C is uniquely determined and automatically associative, and two objects in C are isomorphic just in case they are related by E.)
Your concern is as to size issues. Well, as we can see, we can choose a skeleton for an arbitrary large category precisely if we are in a context where we are allowed Choice for a large number of large collections. If you are in some context where you have Choice only for a small number of choices, you will not be able to obtain skeletons of arbitrary large categories.
It is worth noting that in a framework like ZFC, adding Global Choice (which essentially amounts to allowing Choice for any definable large or small system of choices, each choice comprising a large or small number of options) does not result in the provability of any new statements about sets beyond what was already provable; in jargon, it is a "conservative" extension. That all said, in a set theory like vNBG, which agrees with ZFC on discussion of sets but also explicitly talks about large classes, the Axiom of Choice for sets does not entail the Axiom of Global Choice with respect to arbitrary classes.
