Changing the classifier will not solve your problem. You have to deal with that by, for example, filling your NaN values with average values so as to have all feature vectors with the same length, or by applying more sophysticated methods such as those described in this paper: http://jmlr.csail.mit.edu/papers/volume8/saar-tsechansky07a/saar-tsechansky07a.pdf.
If the feature vectors are not equal size, use must use a factor that take in your accounting the length of vector. the simplest way is divide the result by the shorter length in each computing
you should take all the distinct features from all ur samples to form a common feature vector. Then u build the new vectors for the samples based on the common vector by placing the feature value in the current sample or 0 if not there. Then u can use any classifier u want