[AT&T Samsung Galaxy S 4 Q&A, Help & Troubleshootin] nola mike:
Ok, in my case I had already upgraded to an MLD baseband, and after messing around with some ROMs, couldn't get back into safestrap recovery. I don't know if this will work if you've upgraded to NB1 or NC1, maybe someone else can chime in.

1. Install heimdall. It's in the ubuntu repositories. Also, put the towelroot and safestrap (I used v. 3.72) apks, as well as a kitkat ROM (no need for it to be pre-rooted). Also get the Deadly Venom safestrap kit, version 2 MLD/MK2 and save to your computer. Get the mldmodules.zip file and place on your SD card as well.

2. Download the appropriate firmware. In this case, you're looking for stock MK2/ I337. I got it from this link, and used the 4 separate files in post #1.

3. Untar the files. You can either rename the *.md5 files, removing the md5 extension, or just tar -xvf each file. You should end up with boot.img, cache.img.ext4, hidden.img.ext4, JFLTE_USA_ATT_16G.pit, modem.bin, NON-HLOS.bin, persdata.img.ext4, recovery.img, rpm.mbn, sbl1.mbn, sbl2.mbn, sbl3.mbn, system.img.ext4, and tz.mbn.

4. Put your device in download mode by pressing volume down + power, then letting go of power button. Connect your USB cable.

5. Run the following commands, which I got from here.

sudo heimdall flash --RECOVERY recovery.img --SYSTEM system.img.ext4 --HIDDEN hidden.img.ext4 --BOOT boot.img --no-reboot

I added the no-reboot option because I was able to see the errors on the device screen. I then rebooted back into download mode.

sudo heimdall flash --MDM modem.bin --APNHLOS NON-HLOS.bin --ABOOT aboot.mbn --BOOT boot.img --TZ tz.mbn

At this point I rebooted again, and it booted, but hung at the AT&T logo. I rebooted and it started normally. I didn't actually use the next step.

sudo heimdall flash --CACHE cache.img.ext4

And Poof! You're back to stock. At this point, go to My Files, and find the towelroot apk, and install it. Then install safestrap. Reboot to recovery (power + vol up), wipe everything except your SD under advanced wipe, and install your ROM. Don't reboot here--install the mldmodules.zip file. Now reboot back into download mode.

Unrar (or whatever, I forget how it was compressed) the Deadly Venom kit. You should end up with an MLD directory. Go to the MLD Odin Files directory, and untar the md5 files there. Again, you can rename them first or not. You should end up with:

modem.bin, recovery.img, sbl1.mbn, sbl3.mbn, ap_mld_safestrap.tar, bl_mld_safestrap.tar, boot.img, cp_mld_safestrap.tar.md5, NON-HLOS.bin, rpm.mbn, sbl2.mbn, and tz.mbn.

Ok, so here's where I did some guessing. I don't know how to use Heimdall, and I couldn't make sense of the front end. I did some trial and error, and here's the command that I ended up with that worked:

sudo heimdall flash --RECOVERY recovery.img --BOOT boot.img --ABOOT aboot.mbn --APNHLOS NON-HLOS.bin --MDM modem.bin --SBL1 sbl1.mbn --SBL2 sbl2.mbn --SBL3 sbl3.mbn --TZ tz.mbn --RPM rpm.mbn

Now reboot, and you should be in business. You may need to run towel root again. Oh, and I was getting a lot of weird errors when I was trying to flash with heimdall--I think it ended up being a flaky USB controller on my computer (or maybe a bad USB cable). The install kept hanging. Changing to a different computer solved the problem.

I stumbled through a lot of this, so if there is any redundancy, or if someone wants to improve on this, please do. But hopefully this helps someone...