CAPTCHA's aren't really the best solution as there are tons of scripts that can figure them out.
I'd suggest Spam Karma 2 instead and probably Bad Behavior as well to stop spam bots from getting to your site in the first place.
But if you're really wanting a CAPTCHA, I think you're in luck because unlike GD, I don't think you have to recompile PHP to install ImageMagick. I think all that's needed is that you download the binaries, drop them in a folder, and tell the script where they are. I'm not 100% sure though as it's been a LONG time since I did (my host later added it themselves, so I've had no need to do it myself).
The site's here: http://www.imagemagick.org/