First thing you need to know is that the recovery is compiled into the kernel, so you don't flash a recovery separately, you just flash a custom kernel and you will have a custom recovery after.
The latest stock firmware for this phone is 4.1.2 Jelly Bean, but since the phone is still on the original 2.3.6 firmware, you could flash the old Siyah kernel and use it's recovery to flash custom firmware.
You need to root the phone first. You can root this phone with
Framaroot using the Aragorn exploit. Then go to
this post and download the Tar version of Siyah 2.6.14 Kernel. Flash it in PDA without ticking Re-Partitioning.
Stable custom Touchwiz based firmware available in the development forum are SHOstock or Cooked. Both are based on 4.1.2, and neither are currently supported but both are stable.
If you want something more recent, there are various aosp based firmwares available in the development forum. You may not be able to flash some of them directly from that old recovery in Siyah 2.6.14, but if you need help, you'll have to try to get some help in their threads, because I don't use those.
Happy flashing, and if you need help, ask.