TL;DR: Spray cans don't actually get colder when shaken. However, shaking a can does increase heat conduction from your hand to the can, making it feel colder.
Humans don't actually sense external temperature directly; our thermoreceptors are located under the skin, and thus effectively measure the rate at which body heat is lost through the skin. This is why, for example, touching a metal surface will feel noticeably colder than a wooden or plastic surface at the same ambient temperature.
When you pick up a spray can, it is typically at room temperature, i.e. significantly below body temperature. The can itself is a thin metal cylinder, and thus conducts heat well, but has very little heat capacity in itself. Thus, the rate of heat loss from your hands (and thus the sensation of coolness) mainly depends on how quickly whatever's on the inside of the can will absorb heat from the surface.
Now, a typical aerosol spray can contains a propellant (mixed with the actual payload fluid) which would be slightly above its boiling point (and thus in gaseous form) at room temperature and pressure, but is kept liquid by the elevated pressure inside the can. As the spray valve is opened and the pressure reduced, some of the propellant fluid will boil, bringing the pressure back up until the liquid and gas phases are again at equilibrium.
What this means is that, in a half-empty spray can, the top half of the can will contain gaseous propellant (which, being a gas, will not absorb heat very effectively), while the bottom half will contain liquid propellant (mixed with the payload fluid) at just under its boiling point. This liquid will absorb heat much better than the gas at the top, both because it's denser (and thus has higher heat conductance and capacity), and also because heating it will cause some of it to boil, converting part of the absorbed heat into its latent heat of vaporization. (The boiling effect actually causes a half-empty spray can to act, to some extent, as a diode heat pipe.)
Thus, even without shaking the can, it's possible to observe that the bottom end of a half-empty spray can will feel cooler to your hand than the top end.
Now, when you hold the can and shake it, you cause the propellant liquid to slosh around inside, coating all of the inner surface of the can instead of just the bottom. The sloshing also significantly increases the heat transfer from the can to the liquid, by causing the warmer liquid near the surface of the can to mix with the colder liquid in the interior. (This is essentially the same reason as why moving air feels cooler on your skin than still air.) Thus, a shaken can will generally feel even cooler to touch than either end of an unshaken can.