Is it normal for some classifiers to change their prediction performance from fixed amount of data each time I run them to train?
How are you dividing? You say randomly, but is this being redone each time your analysis is run? If it is, then this is perfectly normal, expected behavior. You're getting a different prediction performance because you have a different random training set each time.

You could also be using a stochastic method, that doesn't give the same result each time, say regression fit using gradient descent versus least squares. Since you didn't give any more details, I can't be more specific than that.