Originally Posted by SamuriHL
I don't know anything about using heimdall. I'd ask in the heimdall thread. And yes, you need both files.
I finally figured it out. The problem was (of course) on my end. Apparently ages ago I installed Kies, which came with its own set of crappy Samsung drivers, and those were interfering with both ODIN and Heimdall (couldn't even flash recovery.) The moment I uninstalled that p.o.s. software, everything started working.
For reference, in order to flash with Heimdall you need to rename the .tar.md5 file to just .tar, extract the 2 BIN files to the Heimdall folder, place the phone in Download mode (Vol Down + Home + Power), connect it to PC, run zadig.exe utility (located in "Drivers" folder of Heimdall), find the GS4 and replace the driver, and finally in command prompt flash with the following:
heimdall flash --APNHLOS NON-HLOS.bin --MDM modem.bin --no-reboot