Each training example has 100 numeric attributes plus one output class and about 80% of the attributes are 'zero' (means no data collected). The value of attributes varies in a small range, like $(-20,20)$. I have 100 examples like this. What method/classifier should I use? I tried KNN, Naive Bayes, SVM, random forest/tree, none of these methods give me accuracy above 50% (I used 10-fold cross validation). What should I do?
This is the well known large $p$ small $n$ problem, often named as $p \gg n$, common in biological, biomedical and imaging problems, basically any field where either data is scarce/expensive to come by or simply carries too much information.
There are several techniques often used in this scenario, such as regularization and attribute bagging. Implicitly, you already tested both, respectively on SVMs and Random Forests. You can try to improve upon that, though. Try other regularization penalties, such as elastic net, try using it fused with attribute bagging.
Another possibility is that your data simply doesn't explain your outcomes.