What type chain lube should you use in a sand and salt water enviroment? I rent bikes in remote beach locations. What lubrication will reduce rust and sand accumulation?
There's not much you can do against the evil trifecta of salt, water, and sand. You can use a teflon, graphite, or moly based dry lube but inevitably sand particles are going to gouge the metal and salt+water is going to start corrosion. 

The problem with chain wear due to sand is that the chains themselves can look good (i.e., not rusty on the outside), but will in fact be considerably worn internally. This can lead to considerable chainring and sprocket wear before you catch it. As other commentators note, one option if you want to keep your current bikes is to buy a chain tool and chain in bulk, and  replace the chains on a regular basis.  

That being said, if you haven't bucked the trend of every other rental place and decided to get the absolute cheapest bikes possible, then you might want to look into belt-drive bicycles. You'll solve at least the problem of chain rusting and sprocket damage from the sand and salt. Your customers will also be impressed with belt-drives as they are silky smooth.

This doesn't solve the problem of salt+water+sand getting in other places (bottom bracket; headset) but the chain is the one part that customers will really notice poor maintenance on.  

However, whether buying a nicer bike is worth it depends on your business model: how much you expect to spend on maintenance and how long you amortize each bicycle given also abuse and theft levels.