(Abridged) Deep NB359 imaging with Subaru by Iwata et al. have detected surprisingly strong Lyman continuum (LyC; ~900A in the rest-frame) from some LAEs at z=3.1. However, the redshifts might be misidentified due to a narrow wavelength coverage in previous spectroscopy. We here present new deep spectroscopy covering the observed 4,000-7,000A with VLT/VIMOS and Subaru/FOCAS of 8 LAEs detected in NB359. All the 8 objects have only one detectable emission line around 4,970A which is most likely to be Ly-A at z=3.1, and thus, the objects are certainly LAEs at the redshift. However, 5 of them show a ~0.8 spatial offset between the Ly-A emission and the source detected in NB359. No indications of the redshifts of the NB359 sources are found although it is statistically difficult that all the 5 LAEs have a foreground object accounting for the NB359 flux. The rest 3 LAEs show no significant offset from the NB359 position. Therefore, they are truly LyC emitting LAEs at z=3.1. We also examine the stellar population which simultaneously accounts for the strength of the LyC and the spectral slope of non-ionizing ultraviolet of the LAEs. We consider the latest statistics of Lyman limit systems to estimate the LyC optical depth in the IGM and an additional contribution of the bound-free LyC from photo-ionized nebulae to the LyC emissivity. As a result, we find that stellar populations with metallicity Z>=1/50Z_sun can explain the observed LyC strength only with a very top-heavy initial mass function (IMF; <m>~50 M_sun). However, the critical metallicity for such an IMF is expected to be much lower. A very young (~1 Myr) and massive (~100 M_sun) extremely metal-poor (Z<=5e-4Z_sun) or metal-free (so-called Population III) stellar population can reproduce the observed LyC strength. The required mass fraction of such `primordial stellar population is ~1--10% in total stellar mass of the LAEs.