There are also the "canonical" nicknames that are not obvious to non-Russian speakers. E.g. Nikolai is Kolja.
So, Aleksandr-Aleksasha. The dropping of "Alek" is the only inconsistent part, on par with Agrippina-Agrusha-Grusha.
It's archaic, used in Peter I times. Modern one is Kolya
One of the potential diminuitives for "Aleksandr" is indeed "Lesha", although I think it's more common as a diminuitive for "Aleksei"?