Packer has a lot of user-friendliness problems (destroying build artifacts on failure, as the OP noted, being just one of them), but it does constrain the universe sufficiently that I can just run Chef and get on with my day.
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.
Consul is...fine, I guess? It's not particularly useful for me, but that's because I have a Zookeeper background and am comfortable with its primitives. I'd use it if I had a need for it. OTOH, I've had extremely bad experiences with Terraform, both in terms of trying to build tooling around it and in having it hose states when resources fail to create correctly (I've mentioned previously around here that multiple clients independently invented the term "terrafucked" for the results of their Terraform state) and I don't feel like I can trust the tool with something as critical as my cloud infrastructural resources. I might bite the bullet and use it if I were working on Google Cloud or Azure, but in AWS, CloudFormation (with tooling on top) is sufficient.