We report on the results of a recent blind search survey for gamma-ray pulsars in Fermi Large Area Telescope (LAT) data being carried out on the distributed volunteer computing system, Einstein@Home. The survey has searched for pulsations in 118 unidentified pulsar-like sources, requiring about 10,000 years of CPU core time. In total, this survey has resulted in the discovery of 17 new gamma-ray pulsars, of which 13 are newly reported in this work, and an accompanying paper. These pulsars are all young, isolated pulsars with characteristic ages between 12 kyr and 2 Myr, and spin-down powers between $10^{34}$ and $4times10^{36}$ erg/s. Two of these are the slowest spinning gamma-ray pulsars yet known. One pulsar experienced a very large glitch $Delta f/f approx 3.5times10^{-6}$ during the Fermi mission. In this, the first of two associated papers, we describe the search scheme used in this survey, and estimate the sensitivity of our search to pulsations in unidentified Fermi-LAT sources. One such estimate results in an upper limit of 57% for the fraction of pulsed emission from the gamma-ray source associated with the Cas A supernova remnant, constraining the pulsed gamma-ray photon flux that can be produced by the neutron star at its center. We also present the results of precise timing analyses for each of the newly detected pulsars.