Extremely metal-poor (XMP) galaxies are defined to have gas-phase metallicity smaller than a tenth of the solar value (12 + log[O/H] < 7.69). They are uncommon, chemically and possibly dynamically primitive, with physical conditions characteristic of earlier phases of the Universe. We search for new XMPs in the Sloan Digital Sky Survey (SDSS) in a work that complements Paper I. This time high electron temperature objects are selected; since metals are a main coolant of the gas, metal- poor objects contain high-temperature gas. Using the algorithm k-means, we classify 788677 spectra to select 1281 galaxies having particularly intense [OIII]4363 with respect to [OIII]5007, which is a proxy for high electron temperature. The metallicity of these candidates was computed using a hybrid technique consistent with the direct method, rendering 196 XMPs. A less restrictive noise constraint provides a larger set with 332 candidates. Both lists are provided in electronic format. The selected XMP sample have mean stellar mass around 10^8Msun, with dust-mass sim 10^3Msun for typical star-forming regions. In agreement with previous findings, XMPs show a tendency to be tadpole-like or cometary. Their underlying stellar continuum corresponds to a fairly young stellar population (< 1Gyr), although young and aged stellar populations co-exists at the low-metallicity starbursts. About 10% of the XMPs shows large N/O. Based on their location in constrained cosmological numerical simulations, XMPs have a strong tendency to appear in voids and to avoid galaxy clusters. The puzzling 2%-solar low-metallicity threshold exhibited by XMPs remains.