If you can't compile mcrypt into php I think there might be some things you could purchase from RSASecurity; however, that will cost you a pretty penny. The other option would be to literally read up on exactly how certain algorithms work (like Diffie-Hellman-Merckle Key Exchange).
It's not the safest; however, it's better than hashing 🙁 The only other thing I can think of is signing messages with PGP or GPG (see: Zend DevZone Article). Not sure if that is anything you want to look in to, or if you have that kind of time.
To be honest, if they don't have mcrypt installed, and they're not willing to install it, there's something wrong. You don't really lose anything by installing it, and you can gain a lot.
As for a dev server, nothing beats getting an older computer (like Dell, Gateway, HP) from Craigslist or Freecycle and throwing CentOS or Ubuntu on there and using that as your dev server. It's what I do. I test locally, upload, final test remotely and then make it "live".