How to handle modeling categorical variables where categories may change over time?
The best way is to just retrain your model. 
Thinking about how a categorical variable affects your model might be helpful. Categorical variables are generally treated a binary variables where each category is its own column, the row in that column is a 1 if that category is present and a 0 otherwise. Now imagine adding an additional column to your data for which your model has not been trained, as would be the case with a new category... this will result in sub-optimal performance. Most likely, this new column will have no affect on the model prediction. 
There are examples of what you are suggesting, but they require a secondary model be fed into a primary model. We see this often in Natural Language Processing, where there is a model for how texts are similar (a word vector) and this model is then fed into another model that predicts things like text category and sentiment. 
So basically, if you can model the similarities of your categorical variables (this is your secondary model), and feed that model into primary model, then you would only need update your secondary model when you get new data. But this approach has its issues...
I am faced with a problem regarding a categorical variable. In my case, my variable may have varying number of levels. For example, suppose, my categorical variable represents type_of_cars. Initially, it had only three types (for argument's sake):gas,
diesel and hybrid. I have used an encoding to represent them. Now a new type of cars come to the market which is eV (for electric vehicle). I want to know if there is a way to accommodate EVs without retraining a model. 
In my case, the categorical variable has roughly 50 different levels and new levels may be added as time goes on or old ones may be deleted. How do I go about modeling the data without retraining the entire model each time it happens, if it is at all possible?
Your suggestions will be greatly appreciated.
Thank you.