Disclaimer: I am the founder and CEO of Boxfuse
If I'm wrong, please let me know how I can write, as I would using Chef and Packer, a set of directives to install and prep Zookeeper, then discover other Zookeeper nodes in my cluster at runtime, while remaining aware of nodes that are replaced due to system failure. (If the explanation exists and involves "our proprietary, closed-source agent," or "our open-source agent that talks to a proprietary backend", you don't have an answer.)
As for the notion of "immutable" servers, this industry term means servers that aren't updated in place, not servers without a read-write file system or read-write memory.
In the case of service discovery with client-side load balancing you can easily integrate client libs for services like Eureka or Zookeeper directly in your JVM application, or you can ship an agent (like Consul for example) and run that. You have a minimal Linux x64 system after all.
And no you don't have to pay $100/month. The licensing is based on a freemium model and your first app is free forever. And at the end of the day all you need to do is make the decision whether those monetary costs outweigh the value you get. And if it doesn't that's fine too. It simply means Boxfuse isn't the right fit for you.
You explicitly asked for suggestions for alternatives. All I did was provide one in case it may prove useful for you.
I'll be honest: I cannot envision a company that should use Boxfuse. Not one. They're better off with something like a Racker template that takes a few parameters and feeds them into Packer than your spooky-action-at-a-distance stuff.