We present Keck/LRIS optical spectra of 17 Lya-emitting galaxies and one Lyman break galaxy at z=4.5 discovered in the Large Area Lyman Alpha (LALA) survey. The survey has identified a sample of ~350 candidate Lya-emitting galaxies at z=4.5 in a search volume of 1.5 x 10^6 comoving Mpc^3. We targeted 25 candidates for spectroscopy; hence, the 18 confirmations presented herein suggest a selection reliability of 72%. The large equivalent widths (median W(rest)~80 A) but narrow physical widths (v < 500 km/s) of the Lya emission lines, along with the lack of accompanying high-ionization state emission lines, suggest that these galaxies are young systems powered by star formation rather than by AGN activity. Theoretical models of galaxy formation in the primordial Universe suggest that a small fraction of Lya-emitting galaxies at z=4.5 may still be nascent, metal-free objects. Indeed, we find with 90% confidence that 3 to 5 of the confirmed sources show W(rest) > 240 A, exceeding the maximum Lya equivalent width predicted for normal stellar populations. Nonetheless, we find no evidence for HeII 1640 emission in either individual or composite spectra, indicating that though these galaxies are young, they are not truly primitive, Population III objects.