The calculation of relative free energies that involve large reorganizations of the environment is one of the great challenges of condensed-phase simulation. Such calculations are of particular importance in protein-ligand free-energy calculations. To meet this challenge, we have developed new free-energy techniques that combine the advantages of the replica-exchange method with free-energy perturbation (FEP) and finite-difference thermodynamic integration (FDTI). These new techniques are tested and compared with FEP, FDTI, and the adaptive umbrella weighted histogram analysis method (AdUmWHAM) on the challenging calculation of the relative hydration free energy of methane and water. This calculation involves a large solvent configurational change. Through the use of replica-exchange moves along the lambda-coordinate, the configurations sampled along lambda are allowed to mix, which leads to dramatic improvements in solvent configurational sampling, an efficient reduction of random sampling error, and a reduction of general simulation error. This is achieved at effectively no extra computational cost, relative to standard FEP or FDTI.