In the $AB_4Q_8$ lacunar spinels, the electronic structure is described on the basis of inter- and intra-cluster interactions of tetrahedral $B_4$ clusters, and tuning these can lead to myriad fascinating electronic and magnetic ground states. In this work, we employ magnetic measurements, synchrotron X-ray and neutron scattering, and first-principles electronic structure calculations to examine the coupling between structural and magnetic phase evolution in GaMo$_4$Se$_8$, including the emergence of a skyrmionic regime in the magnetic phase diagram. We show that the competition between two distinct Jahn-Teller distortions of the room temperature cubic $Foverline{4}3m$ structure leads to the coexistence of the ground state $R3m$ phase and a metastable $Imm2$ phase. The magnetic properties of these two phases are computationally shown to be very different, with the $Imm2$ phase exhibiting uniaxial ferromagnetism and the $R3m$ phase hosting a complex magnetic phase diagram including equilibrium Neel--type skyrmions stable from nearly $T$ = 28 K down to $T$ = 2 K, the lowest measured temperature. The large change in magnetic behavior induced by a small structural distortion reveals that GaMo$_4$Se$_8$ is an exciting candidate material for tuning unconventional magnetic properties $via$ mechanical means.