Are there any water softening devices that really work on
exceptionally hard water without using salt?

You might want to investigate ScaleBan:

http://www.lehmierelectric.com/cgi-bin/ebo.cgi/scaleban.html

Pseudoescientific nonsense.

I suspect kottekoe is right. That's why I used the word "investigate."

"hard" water contains dissolved calcium ions.  Most water softening
systems use ion exchange to replace the calcium ions with sodium ions,
and use salt (sodium chloride) as a source of sodium.

In principle, you could replace the calcium with other ions to avoid
sodium, but I suspect that these methods would be either more
expensive or have other drawbacks.  For example, you could replace the
calcium ions with hydrogen ions (H+) but that would acidify the water.

Distillation will remove the calcium without adding anything, but is
generally much more expensive than ion exchange.

Any "cheap and easy" method of removing calcium from hard water is
likely a scam, especially if magnets are involved.

Closer examination of the claims made on the ScaleBan page (to which I
linked above) have led me to believe that it is, indeed,
pseudoscientific nonsense that is not worth much investigation.

You could attempt to filter the water through something like reverse
osmosis, but it is super inefficient probably for your applications.

Remember that as fstokens mentioned, hard water contains calcium
salts.  You are replacing the calcium with sodium, so technically,
hard water already contains salt (not sodium chloride, but chemically
speaking, they're still salts)

Reverse osmosis will do it.  The hard water is pumped through a bundle
of semi-permeable membranes.  The porosity through the wall is small. 
Water molecules pass through, but large calcium molecules do not. 
Pure water is collected outside the tubes.  The concentration of the
hard water increases and will have to be rejected and disposed.

This company manufactures water softner says " Unlike sodium based
water softeners the Aquafer uses no salt or electricity to treat hard
water scale"
check it out, URL is    http://www.aquaferwater.com/
Hope this is of some help to you.

You can try ion exchangers for softening the water without salt. It
removes all the ions(and thereby salts) presents in the water within a
short time and it will be economical too.
For more details, visit http://www.lenntech.com/ion_exchanger.htm

There is distillation and bottled water.  Both expensive.