I think you have offered the solution, more or less, yourself.
You can store the captcha on the server based on (1) a key, (2) an encoded timeout stamp, (3) the IP address of the caller, and (4) possibly some identifying information in the caller's browser identification (browser + version number). That should be pretty unique and hard (not impossible, but hard) to spoof.
Needless to say, you have to keep the timeout period very short, say 15 seconds or so.