Is there some generalization of multi-level analysis to multiple categorical variables? The classical case for Multi-Level Models are data domains where each 'individual' belongs to some group, like pupils to school classes. In such a case, the individuals are distributed into disjoint buckets like this:
---------------------------------------------
|  Class1  |  Class2  |  Class3  |  Class4  |
---------------------------------------------

I need a way to extend that concept to a domain where multiple categorical variables are present, like pupils that belong to classes and gender:
        |  Class1  |  Class2  |  Class3  |  Class4   |
-------------------------------------------------------
Female  |   0.71   |   0.42   |   0.67   |   0.65    |
-------------------------------------------------------
Male    |   0.75   |   0.44   |   0.82   |   ? (*)   |
-------------------------------------------------------

Here, every pupil belongs to one 'gender bucket', as well as one 'school class bucket'. 
I need that to predict missing values based on the known data. In the example above, we can see that the performance of the male pupils is slightly above the performance of the females (for example in Maths). The performance of class 4 is about average, and it's very similar to class 3, so we expect the missing value for the males in class 4 to be about 0.75.
The model should be able to recognize such patterns, like the general performance difference between males and females, as well as the performance difference between the school classes. The prediction should be based on these differences.
Is there a generalization of Multi-Level Models for such a case? Or maybe some other tool?
To be clear: I need a model with much more than two categorical variables, and I don't know which of those variables are more important than others.
EDIT: To make it clear, I don't want to generalize among any of these categories. I'm not interested in any aggregated value (total performance of all females, or total performance of class 4). I'm interested in predicting the performance of the males in class 4. Both my sex and class variables are fixed effects. Maybe this question doesn't have anything to do with MLMs.
 A: The model exists and is often referred to as crossed random effects. However, I don't think it is feasible for your application: computation time increases extremely fast with the number of dimensions. 
In your example I would just use a simple linear regression model including a categorical variable for class, gender and the interaction.
A: This question doesn't really have anything to do with MLM as it stands now. You're just predicting grade with class and sex. You just just want to look up data imputation. There are loads of methods there. When you've read a bit on that, if you have trouble, come back here and ask another question.
You should keep in mind that the best methods of data imputation will not have a fixed value to stick into your missing data slots; rather they will define the probably distribution from which the value should come from.
Old answer in case you really do have some random grouping variables you haven't identified
It's not just that each data point belongs to some group in MLM but that the group they belong to is a random variable. Simple between subject designs have each individual in some group, just like your male / female sex variable. But class is a variable that you define in an MLM as a random variable. You don't have predictions for the values in each class, nor do you typically particularly care about them. The classes are a random sample of possible classes for which you will care more about the estimates of the variance than any particular class. The goal is to generalize across classes. Your sex variable is clearly not a random sample of sexes and you don't plan to generalize one value across the many sexes.
Without knowing more about your design it's hard to say whether your other categorical variables are more like class or sex but I'm guessing that they're the latter.
Therefore, your would simply model this with sex as a fixed effect and class as a random grouping variable that your fixed effects are nested within. In lme4 package in R the model would look something like:
lmer( grade ~ sex + (sex|class), data = dat )

That's grade predicted by sex and also both sex and intercept grouped by class as random effects. I've allowed sex to both be fixed and randomly vary by class (but that doesn't make it the random variable).
There are a variety of papers that will teach you basics of MLM. If you can just read basic linear model syntax and don't want to see any matrix modelling thrown up then you might find the early sections of Barr et al (2013) very educational.
If you construct a model like the above you can get missing values filled in by taking predicted values from the model. After you get that far you should search for methods of getting predicted values from your model to fill in your missing data.
Barr, D. J., Levy, R., Scheepers, C., & Tily, H. J. (2013). Random effects structure for confirma- tory hypothesis testing: Keep it maximal. Journal of Memory and Language, 68, 255-278. doi: dx.doi.org/10.1016/j.jml.2012.11.001
