The only Verizon Galaxy S4 release that permits a custom recovery is a phone with the original MDK bootloader. Not checking first to tell what's installed before flashing will often break your phone.
1. What releases are there, and how can you tell what you have?
There are currently 7 different releases of the firmware for the I545.
- VRUAMDK (Usually called just "MDK")
- VRUAME7 ("ME7")
- VRUDMI1 ("MI1")
- VRUEMJ7 ("MJ7")
- VRUEMK2 ("MK2")
- VRUFNC2 ("NC2")
- VRUFNC5 ("NC5")
There's another release that was apparently a leak or limited release, MG7.
You've got to know what bootloader and firmware you have installed before you do anything. The bootloader is the critical thing, but unless you're using a MDK bootloader, chances are that the bootloader on your phone is the same as the build version. To figure out what you're running, use the "Settings", "More", "About phone" menu. In most cases, the "Baseband version" displayed and the "Build number" will be the same, which tells you what build you're on. The best way to tell what bootloader you have is to install an app - "Phone INFO *Samsung*" and "Phone info" will both tell you what build and bootloader you have.
The "Developer Edition" devices have "I545OYUA" build numbers versus the consumer versions, which start with I545VR.
Once you're on a particular build, it is not possible to downgrade to an earlier release. The single exception to this is that you can flash MJ7 over MK2, but that's it.
If you're past MDK, you can't bypass the bootloader until an exploit is found.
If you start flashing things without verifying that it's for the release on YOUR phone, you risk bricking it. There's dozens of youtube videos telling you how to flash custom recovery on your phone that WILL NOT WORK unless you're on the MDK bootloader. Be sure to comment in the youtube thread after they assist you with bricking your phone.
If you need to tell for sure what bootloader you're on, you can use applications like "Android System Info" (Open the "System" tab and the "Buildinfos" and look for Bootloader), or from a shell by using the command "getprop ro.bootloader". Use either adb shell or the "Terminal Emulator" app to do that.
2. What can you do with your phone?
For MDK, root using this link. or this link.
For ME7, root using this link.
For MI1, root using this link.
For MJ7 and MK2, root using this link.
For NC2 and NC5, you can't currrently root unless you downgrade the baseband to MK2.
If you want to install a custom recovery, you MUST have the MDK bootloader. Follow the MDK link above.
If the bootloader isn't "I545VRUAMDK" you have a locked bootloader and can only use Safestrap to install custom ROMs. Custom recovery is not possible. Attempts to install custom recovery will soft-brick your phone and require you to re-flash a stock ROM.
Information on Safestrap is available in this thread.
Recover by re-flashing stock
For MDK, Follow this link.
For ME7,Follow this link.
For MI1, Follow this link.
For MJ7, there's a no-wipe and a full wipe image.
For MK2, Follow this link.
Flash new Modems
The firmware that runs the phone's radios, which allows you to connect to the networks (CDMA, LTE, WiFi, Bluetooth) can be updated independently of the bootloader. Flashing the MJ7 modem can get you new LTE bands, for example. Read here for information on available modems.
3. What to avoid
Every carrier's version of the Galaxy S4 is different. Things that work for the Sprint, AT&T, T-Mobile, and other carriers phones may not work on the Verizon version and can lead to bricking your phone. Don't do things just because it works on the T-mo, AT&T, or sprint phones unless you don't care if your phone is rendered useless.
Regardless of what you read, recommendations to use Goo Manager to flash custom recovery will not work and will soft brick your phone unless you're running the MDK bootloader. Don't do that.
If you manage to do the wrong thing and soft-brick your phone, search the Android Development forum for a factory image that can be flashed to recover it based on what baseband you started with.
For example, this image for MJ7 (Android 4.3).