What is the best way to optimize the parameters in a Sklearn classifier, when I have little data?
You can't get around the test/train thing. I guess in your case, the problem is the choice of method. When I read your data description, I suspect that you might achieve better results with regularization, e.g. Lasso. See some examples here.

Basically you would apply a multiclass logit with lasso penalty in your case. Alternatively you could also check boosting with lasso (aka $l1$ penalty). Here is some playcode with the iris data.

Since your data has many columns and not so many rows, I might go for lasso (not ridge or elastic net), because lasso can shrink features to zero if they don't make a meaningful contributin to the classification. This is especially helpful with high dimensional data.