How can I make a prediction in a regression model if a category has not been observed already? I'm researching a regression model to predict a target value that has four features, all of which are categorical.

The categories are not fixed, e.g. one is a customer identifier. How could my model handle making a prediction for a customer identifer it hasn't seen before, based on the remaining features it has been trained with?

I have considered having a model for each of the features that could predict which category label is most similar based on the other three remaining features (or multiple similar category labels could be used and take an average of the target values for those).

My only concern with with this method is that it's not that scalable, I'm going to want to extend the model with more and more categorical features.

Is there some technique that could create an 'unknown' label for each of the features so the model can handle this case or would the prediction likely be completely inaccurate?
Technically, you can't. That is one of the limitations of regression models; they are really only effective for values/ranges that they have seen before. Your use of categorical values makes it even more complex. But even with continuous variables, it is not recommended to use regression models for these "unknown" values.