How can I make a prediction in a regression model if a category has not been observed already?
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.