Validation dataset is not a random sample from whole dataset I am facing a small dataset to do machine learning. The small dataset is not the dataset on which ML will be applied. It is a derived dataset on which the model will be trained. However, due to derived nature, part of dataset will be discarded. In particular, some of the sample in training will never show up in the validation set as there are not enough observations for those samples not in validation set. Normally, the validation requires a random subsample from total dataset.
Q: Can I train model based upon the training set and test on a validation set which is necessarily a random split from total dataset? Discarding data is very bad in my case. In particular, I want to do a random split on a subset of total dataset and keep data short of observations in training at the same time.
 A: 
some of the sample in training will never show up in the validation set

If I understand you correctly, you have samples (specimen, cases) of which you have multiple observations each.
In that case, observations of the same sample may be more similar to each other than to an observation of a different sample (of the same outcome/class/label). Thus, any sample (i.e. all observations of this sample) should be either training or test data, but a sample used for training a (surrogate model) should never show up in the test data for that particular (surrogate) model.
That is, if you want to use the model to predict new unknown samples, then new unknown samples are what you need to estimate generalization performance.

Normally, the validation requires a random subsample from total dataset.

No. Validation requires samples that allow you to measure the generalization performance for the data generation process/application you care about.
A random split, e.g. as done in standard CV procedures, may be the most convenient way of setting aside a data set for (internal) validation/verification, but there are actually more sophisticated ways. You may obtain validation data that was designed (as in design of experiments) to measure particular performance characteristics you are interested in. (That design may contain random elements.)
Moreover, there are situations where one wants to determine performance for samples that were excluded from training in a systematic way.
As an example, I've been working with Raman spectra. They sometimes have artifacts caused by cosmic rays hitting the instrument while measuring (cosmic ray spikes). I often exclude spectra with such spikes from model training as being of bad quality - but then during validation measure whether/how rugged (robust) the predictions are wrt. such spikes.
Similarly, you may train a model on lab samples and then verify/validate on field/process samples to find out whether you can use it for predicting field or process samples. (Whether better performance could be obtained by training on field/process samples is a different question)

Note that I'm using validation as in determining whether the obtained model is fit for purpose.
