The cynical side of me feels like the only real solution might be to just yoink every single child out of there, and then let them grow up in a place where the centuries' worth of nonsense doesn't mean anything. There are groups that work today to get Israeli and Palestinian kids to meet up and interact, for the purpose of letting them see that the other side is *GASP* just like them. The problems only start after they go back home to the culture that produces the self-fulfilling cycle of hatred. So just get them out of there, and tell the adults that they'll only be given back if everyone can get the hell over this bull****. If they can manage that, great. If not...well, you just let time take its toll, and either way, the conflict ends with that generation, and the next one gets a fresh start.
(Obviously this is by no means a reasonable or conscionable solution.)