How can I do classification with categorical data which is not fixed?
It is very good question; in fact this problem has been around for a while and I have not yet found the perfect solution. Yet more than happy to share my experience: 


Avoid one-hot-encode as much as possible (contrary to what was suggested above). The reasoning is that it won't work. A model with one-hot-encode features only works when all those sublevels had been existed in the training data. The model won't be able to do prediction, unless somehow it is manually tweaked. If you search you will find many people ran into this issue when splitting their data into train/test, and faced the issue of some sublevels of a particular feature were not present in the training split and subsequently failed to do prediction on the test. Said aside, if you have very high cardinal features (maybe like your city with let's say 200 city names), this will increase the dimensionality of your data unnecessarily! If for some reasons you may need to do one-hot-encoding, just keep these in mind.
Use Other Encoding Methods. Maybe try learning more about other methods that are robust to this issue, at least for the time being like target-based coding, hashing (see some references below). If you are with Python there is a nice package offer mant encoding options. You may be surprised to see that other simple methods often works just fine.
Retrain your model. Theoretically when learning your train/set should have had the same distribution (mostly this is thought of as target distribution, but can be true about variables as well). Now with new items comes into play, your test (unseen) data distribution has changed. Then it is best to retrain the model again so that those new cities will be accounted for. 
Put Newly Added Subcategories (and least frequent ones) to Others. While earlier point is true theoretically, it is very likely that the test distribution (of that particular category) won't change that drastically in most of the cases e.g. very few items goes top of the categories in the training set. Perhaps like in your case, you may have 100 cities in the city feature, and just very few new ones comes over time. What I would consider would be looking at the let's X-quantile of that particular category, and put the least frequent ones into Others subcategory. Assuming your newly added data point is only little, it will very much goes into the Others group. You will certainly lose a level of granularity by doing this one, but once again the point of learning is that not only your model learn the training data, but most importantly to be able to generalize very well on unseen data and if those new added categories are very data points, grouping them altogether into the Others group won't hurt. 
Other Recent Not-Yet Mature Solutions like Cat2Vec (borrowed from Word2Vec from NLP) or Similarity Encoding. These are very recent, check the paper for the former and its github and an example (based on Word2Vec) in Kaggle, and this paper for the latter and its implementation. The idea of the former is to convert categories to vectors. As much as I have to say it really make sense to work, but I have no experience using it. The latter, so-called dirty_cat, looks quite promising and easy to use. Whether it is robust to having unseen cardinal category in your test data is not clear to me!


P.S.: I would like to add that the idea of city to a geographical location given in the first comment is really nice and it is actually not complicated as they are many Python API e.g. by Google or HERE that allows you to do that. But it is noted that this is just a way to engineer new features and certainly not to be replaced by the city feature itself.

Interesting references to check first, second, third, fourth (no particular order!)

All above-mentioned points are practical solutions rather concretely theoretically correct, and surely subject to further discussions. And I am more than happy to learn more.