Is there any chemical substance, whose solubility increases with decrease in temperature ?
Gases are usually more soluble at lower temperature, in fact there are some solid substances the show this behavior too. The classical example is $Cerium \space III sulphate$ $Ce_2(SO_4)_3$. This behavior is due to the fact that $Ce_2(SO_4)_3$ has an exothermic Heat of Solution. So for the principle of Le Chatelier increasing the temperature cause a decrease of the solubility of the salt that tend to compensate the increment of temperature absorbing energy through the formation of a precipitate, that in this case is an endothermic process.
These substance are not so common, however if you deal with sulphate, selenate or some strange metals you should take a look in literature checking if they have this behavior. As suggested Nicolau Saker Neto I've check the wikipedia list, I've made this plot from there, in the Y axis is shown how much the substance is soluble in water as grams dissolved per 100 grams of water:
The solubility of a solid depends on the temperature in the following way: When the net dissolving heat is negative (i.e. when heat is given off by the dissolving process) the solubility is higher at lower temperatures because the energy is more readily absorbed by the dissolving medium. This works analogously the other way around (and is usually more the case, as you seem aware of).
For gases the relationship is usually the other way around (increase in temperature results in a decrease of solubility).
The reason for this gas solubility relationship with temperature is very similar to the reason that vapor pressure increases with temperature. Increased temperature causes an increase in kinetic energy. The higher kinetic energy causes more motion in molecules which break intermolecular bonds and escape from solution.
Further explanations (and the source of the quote above) can be found here.