We performed detailed chemical abundance analysis of the extremely metal-poor ([Ar/H]-2) halo planetary nebula H4-1 based on the multi-wavelength spectra from Subaru/HDS, GALEX, SDSS, and Spitzer/IRS and determined the abundances of 10 elements. The C and O abundances were derived from collisionally excited lines (CELs) and are almost consistent with abundances from recombination lines (RLs). We demonstrated that the large discrepancy in the C abundance between CEL and RL in H4-1 can be solved using the temperature fluctuation model. We reported the first detection of the [Xe III]5846 A line in H4-1 and determination of its elemental abundance ([Xe/H]>+0.48). H4-1 is the most Xe-rich PN among the Xe-detected PNe. The observed abundances are close to the theoretical prediction by a ~2.0 Msun single star model with initially r-process element rich ([r/Fe]=+2.0 dex). The observed Xe abundance would be a product of the r-process in primordial SNe. The [C/O]-[Ba/(Eu or Xe)] diagram suggests that the progenitor of H4-1 shares the evolution with two types of carbon-enhanced metal-poor stars (CEMP), CEMP-r/s and CEMP-no stars. The progenitor of H4-1 is a presumably binary formed in an r-process rich environment.