Assume I have 1000 samples of data. I split the data randomly into training and test sets of size 800 and 200, respectively. Now, I train a classifier using the training set, and then evaluate the performance of the classifier using the test set. Assume I am not satisfied with the results. So, I change some parameters, and do this again. Is the approach wrong? Should I have split the 800 samples into another two sets, fine-tune model, and only then try it on the test set? What if my sample is too small for two splits? The data is split randomly, so I assume this would not be completely wrong?
The required data points is a function of noise and desired accuracy. The approach you outline is almost correct, but you're likely to end up overfitting if you're adjusting parameters after seeing all of the data.
The usual approach to cross-validation is to divide the data into two segments. The first segment might comprise 800 observations. This segment is split up further into your training dataset, that the algorithm learns parameters from, and your validation dataset, that you consult to adjust hyperparameters.
The 200 observations that were left out of this should be stored far from any of your model development code. Once you're completely finished altering the parameters you evaluate the final performance of your model on these 200 observations. This is the reported error of your model.
Splitting the dataset randomly isn't necessarily a wrong approach. AFAIK it's just a less popular alternative to k-fold cross-validation.
There's an excellent chapter on cross-validation in Elements of Statistical Learning (PDF). See pages 241-254.
It is wrong to change your model after you've tested it on your test data. There are some technical ways to approach this, but it's easier to think about intuitively.
If you use out-of-sample data to make changes to your model, it is no longer validly considered out-of-sample. Think about it: the point of a test set is that the test data is analogous to "new" data. Thereby it's a better estimate of out-of-sample prediction error than some in-sample approximation like AIC. Once you've fitted your model to it, or made changes based on it, it's no longer new data.
Unfortunately it sounds like you've burned your test data. At the very least you should re-split the data and try again.
And yes, this is why people use 3 splits: training, test, and validation. One to fit the models and make changes (preferably you still don't iterate here, but usually it's unavoidable), one to compare models (but not make any changes), and one to demonstrate the effectiveness of that model. See here.