Even after flashing clockworkmod, when I go into the recovery menu after booting, it just gives me the stock recovery system. Help? I've also tried with twrp, no luck.
This is because most stock systems will flash the stock recovery on boot and/or your bootloader is locked (and prevents writing to safe partitions).
Please follow this instructions from CM; They are working, I already tested them: http://wiki.cyanogenmod.org/w/Install_CM_for_jflte#Recovery_Installation
You most probably using odin and cwm or twrp tar.md5 file to flash new recovery to a Samsung device. Key point in here is that untick the reboot after flash in odin settings and remove battery after flash completed. This way original recovery doesnt have time to reinstall.