The origin of magnetic fields in clusters of galaxies is still a matter of debate. Observations for intracluster magnetic fields over a wide range of redshifts are crucial to constrain possible scenarios for the origin and evolution of the fields. Differences in Faraday rotation measures (RMs) of an embedded double radio source, i.e., a pair of lobes of mostly Fanaroff-Riley type II radio galaxies, are free from the Faraday rotation contributions from the interstellar medium inside the Milky Way and the intergalactic medium between radio galaxies and us, and hence provide a novel way to estimate average magnetic field within galaxy clusters. We have obtained a sample of 627 pairs whose RMs and redshifts are available in the most updated RM catalogs and redshift databases. The RM differences of the pairs are derived. The statistically large RM differences for pairs of redshifts z>0.9 indicate that intracluster magnetic fields are as strong as about 4{mu}G. Such strong magnetic fields in the intracluster medium at the half age of the universe, comparable to the intracluster field strength in nearby galaxy clusters, pose a challenge to the theories of the origin of cosmic magnetic fields.