Two-dimensional metals offer intriguing possibilities to explore metallicity and other related properties in systems with reduced dimensionality. Here, following recent experimental reports of synthesis of two-dimensional metallic gallium (gallenene) on insulating substrates, we conduct a computational search of gallenene structures using the Particle Swarm Optimization algorithm, and identify stable low energy structures. Our calculations of the critical temperature for conventional superconductivity yield values $sim 7$ K for gallenene. We also emulate the presence of the substrate by introducing the external confining potential and test its effect on the structures with unstable phonons.