I forgot to address this earlier:
That level looks like its using 32 pixel wide sprites for those column rock patterns, so 96 pixels in lines where 3 columns align leaving 160 pixels for other sprites. (a maximum of 10 16 pixel wide sprites without flicker/drop-out, or 5 32 pixel wide sprites -and the player and most items look like 32 pixels wide, though some enemies look like 16 pixels)
You also forgot to mention the parallax at 4:50-5:40)
Stages 1 and 2 are generally just using the single "layer" simulated with animation (in addition to the foreground scrolling), but stage 3 had the "background" section animate several overlapping layers.
(see 2:44 -level 6 is another good example at 6:53)
Some stages also have diagonal scrolling on the far BG. (I mean specific animation when the player moves diagonally, not just the animation moving diagonally)
On another note, Metal Storm also has some serious problems with music being cut off by SFX. (the entire lead is often cut-out -seems like many SFX use both pulse wave channels)
You can't do that with the NES though . . . you'd have to rely in remapping tiles to other tiles (and general mapper functionality) unless VRAM was added on-cart. (in the latter case, the animated tiles could be limited to VRAM)
Plus (without special mappers) the NES has the 16x16 color attribute limitation . . . and you don't have scanline/raster interrupts to facilitate palette swaps either (at least without added hardware). SMS had the latter problem too iirc.