The mean running time is usually not used in average-case complexity theory because it is not well-behaved under changing the model of computation. Your $(n!)!$ example is in the class $Heu{r}_{neg}P$. For a good overview of average-case complexity theory see Bogdanov and Trevisan.