A large output layer is necessary for NLP tasks, where there are a lot of possible output classes such as words.
How much more expensive is the normalization in comparison to the matrix multiplication required to generate $N$ outputs of the softmax layer? Both the matrix multiplication and normalization scale linearly with $N$.
There are techniques, such as Noise Contrastive Estimation and Self-Normalization, which approximate the probability values of the softmax layer. However these only affect the normalization and I'm not aware of any others that would affect the matrix multiplication.