Is there a model that can adapt to additional new training data with different columns? My training data comes in batches. Sometimes, new batches (completely new samples) come with new columns that are not in old batches, or they may be missing some of the old columns.

For example, suppose there are two ingestions. In the 1st ingestion, we have ETL on a set of fields. In the 2nd ingestion, we have added a new field and we are not allowed to ingest and update the old records again (they may have been deleted for good).

Ideally, I want to train a classifier using all batches of data. What kind of algorithms would perform well under this scenario.
A tree-based algorithm can do that.

The point is that you need to train the model with the union of the possible columns that can exist the different batches.

Moreover you need to account for missing values so that the model can learn to recognize a missing and handle them: you need to recode the missings with a proper value, for example you can create a new level for categorical variables and recode the numerical in the standard way (zero, mean, extreme value, etc.)