Are there ways to increase computational performance of a normalized least squares (NLMS) filter? Multidelay block frequency-domain (MDF) filters have been proposed to do this, but they also take away from convergence speed and accuracy, because they only update the estimated impulse response once every block, not once every sample. Are there any other methods?
If you want to implement the "standard" NLMS algorithm without cutting any corners, then you're probably not going to find a structure that is significantly more efficient. Block forms of LMS filtering aim to use fast convolution techniques (like overlap-save or overlap-add) to speed that part of the process. However, as you noted, the filter coefficients are only updated per block, as the filter must be constant over the block to use the fast convolution approach.
The highly recursive nature of NLMS is going to limit you if you want to keep the sample-by-sample update characteristic. While the filtering action is non-recursive, the filter coefficients at time instant N are a function of the coefficients at time instant N-1, which limits your ability to speed the process by using parallelism or block-oriented computation. As in most cases, there isn't a free lunch: if you want pure NLMS, then you're best off just implementing that.