They could have shipped both HALs. Or made it easy to switch which one was in use without reinstalling.
CDs were around and hard drives weren’t that small at the time. (Or maybe the really early SMP versions predated widespread availability of CD-ROMs, but I remember dealing with this nonsense and reinstalling from an MSDN CD set.)
With NT4, I'm pretty sure both HALs were on the CD-ROM (unless you had an exotic system with a custom HAL, which came with its own install media). Keep in mind your use case is approximately nobody, you either had a SMP system or you didn't.
It was really not that rare to want to move a disk from one system to another. Except that there was an obnoxiously high chance that Windows would refuse to boot.