Is it k-fold where k=10 repeated k times?
Is it leave-one-out?
Is it a different method?
The crucial point here is less k-fold vs. LOO (though I'd usually recommend k-fold over LOO) but whether you split into independent sets of cases or not. If not, you can be subject to large overoptimistic bias, i.e. you then get a very bad estimation procedure.
Should the hyper-parameters be re-tuned for each round of k-fold cross validation?
Typically: yes. That is, as soon as any optimization driven by the data at hand is done, this must be re-done for every surrogate training set. It is actually part of the full training procedure.
Exception: if you fix the hyperparameters by knowledge that is entirely external to the data set at hand. E.g. if from analyzing, say, previous runs of experimental data, and decide to go with those hyperparameters without re-optimizing on the data at hand, you just use them and that's it.
In leave-one-out cross validation should one instance be left out from one class at a time, or both classes at the same time?
The term leave-one-out is normally defined to mean that in total one case is left out. However, you can use a "stratified leave-two-out" validation where from each class one case is left out. Whether or not I'd recommend one or the other depends on further circumstances. E.g.
- How sensitive do you expect the model to be wrt. relative class frequencies? Then a stratified approach that strives to keep the relative frequencies correct may be better.
- Are the relative frequencies of your classes representative for the application?
- Are you in a situation where measuring model stability is crucial? This is not possible with LOO, but it becomes possible with iterated/repeated leave-2-out (or iterated/repeated k-fold CV)