Is there a soluble salt, or compound that when dissolved in water results in a solution with density less than pure water?
No, you can't dissolve a salt to make a lower density solution.

Instead of thinking about salt ions just fitting into water molecules, think about it as if the salt ions are letting everything fit together better. The water molecules are achieving their current density because of the presence of hydrogen bonding. When you add the ions you introduce better bonds between the charged ions and the polar water molecules. These bonds allow everything to fit together tighter leading to a rise in density. 

This decrease in overall bond length is a key to the spontaneity of the solvation reaction. If you introduce an ion that increases the bond length you would see no solubility because they system would be more energetically stable as a bulk solid and water with hydrogen bonding. 

The polyelectrolyte you bring up raises a good point, but it is not an exception to this rule. Instead, the polyelectrolyte is so large that it "solvates" into water to form a gel. This new material is not really a solution so much as just a new material with water in it. Hydrated salts would be another example. 

This should be the case for all solute-solvent systems. However, this is not to say what you want can't be done. You may have to looks at some reversible reaction or cis/trans type switching material. A simple solute-solvent system won't get it done.