How to Improve Least Means Squares (LMS) / NLMS Filter Performance?
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.