We describe a search for H-alpha emission-lined stars in M31, M33, and seven dwarfs in or near the Local Group (IC 10, NGC 6822, WLM, Sextans B, Sextans A, Pegasus and the Phoenix dwarf) using interference filter imaging with the KPNO and CTIO 4-m telescope and Mosaic cameras. The survey is aimed primarily at identifying new Luminous Blue Variables (LBVs) from their spectroscopic similarity to known LBVs, avoiding the bias towards photometric variability, which may require centuries to manifest itself if LBVs go through long quiescent periods. Followup spectroscopy with WIYN confirms that our survey detected a wealth of stars whose spectra are similar to the known LBVs. We "classify" the spectra of known LBVs, and compare these to the spectra of the new LBV candidates. We demonstrate spectacular spectral variability for several of the new LBV candidates, such as AM2, previously classified as a Wolf-Rayet star, which now shows FeI, FeII and Balmer emission lines but neither the NIII 4634,42 nor HeII 4686 emission that it did in 1982. Profound spectral changes are also noted for other suspected and known LBVs. Several of the LBV candidates also show >0.5 mag changes in V over the past 10-20 years. The number of known or suspected LBVs is now 24 in M31, 37 in M33, 1 in NGC 6822, and 3 in IC 10. We estimate that the total number of LBVs in M31 and M33 may be several hundred, in contrast to the 8 known historically through large-scale photometric variability. This has significant implications for the time scale of the LBV phase. We also identify a few new WRs and peculiar emission-lined objects.