The other option (just spitballing here) would be to put a cap across the coil. It slows down the coil release. Not very useful if you need the relay to release fast, but I have used it in a couple of oddball cases over the years.

Andy