Extremely metal-poor (XMP) galaxies are defined to have a gas-phase metallicity smaller than a tenth of the solar value (12+{log}[{{O/H}}]\lt 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; metals are a main coolant of the gas, so metal-poor objects contain high-temperature gas. Using the algorithm k-means, we classify 788,677 spectra to select 1281 galaxies that have particularly intense [O iii]λ4363 with respect to [O iii]λ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 has a mean stellar mass around {10}8 {M}ȯ , with the dust mass ∼ {10}3{M}ȯ 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 (\lt 1 {{Gyr}}), although young and aged stellar populations coexist at the low-metallicity starbursts. About 10% of the XMPs show 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.