Cellular lightweight concrete (CLC) offers significant advantages for sustainable construction, including reduced structural weight and improved energy efficiency, yet maintaining adequate mechanical performance remains challenging. This study investigates the combined effects of fly ash (FA) and polypropylene fiber (PPF) on the mechanical properties of lightweight mortar as a CLC analogue. Nine mix variations were prepared with FA substitutions of 0%, 10%, and 15% and PPF contents of 0%, 1%, and 5% by cement weight. Compressive strength and elastic modulus were measured at curing ages of 7, 14, 28, and 56 days. The optimal mixture, which included 10% fly ash (FA) and 5% polypropylene fibers (PPF), exhibited the highest compressive strength, reaching 1.116 MPa at 28 days and 1.130 MPa at 56 days—corresponding to increases of 31.6% and 32.6% over the control mixture (0.848 and 0.852 MPa, respectively). The elastic modulus of this mixture increased to 134.9 MPa, substantially higher than that of the control (56.25 MPa), indicating enhanced stiffness and resistance to deformation. These improvements result from the pozzolanic activity of FA, which refines the pore structure and promotes calcium silicate hydrate formation, and from the microcrack-inhibiting action of PPF. Other mix variations failed to meet the minimum target compressive strength of 1 MPa, likely due to non-uniform mixing or suboptimal curing. The results demonstrate that the strategic combination of FA and PPF effectively improves the mechanical performance of lightweight concrete, offering valuable insights for the design of sustainable, high performance construction materials.