Let me quote Titus Maccius Plautus to begin this one, ““Patience is the best remedy for every trouble”, yes AT&T did put us in trouble when the locked the bootloader on their Galaxy S4, but djrbliss had other thoughts, he bypassed it and released Loki.
Now AT&T users have the option of installing either ClockworkMod or TWRP; installation of TWRP is as simple as below:-
1) Install GooManager from the Play Store
2) Open GooManager and provide root permissions
3) Hit Menu (or the button with the 3 dots on your screen) and then Install OpenRecovery
More details about TWRP for AT&T Galaxy S4 can be found here.
To install ClockworkMod you need to be a bit more careful and follow the instructions here.