This is a major problem with perl, one that is to be resolved in Perl6.
That said, I have a couple suggestions:
Have you tried backslashing the dollar signs? Then it won't (rather shouldn't... I haven't had this particular perl experience) evaluate them until you call it. But I doubt that will work. There is a way to evaluate perl code in a regular expression, but I can't recall it. I feel it was something like curly braces around the expression, but don't trust me there.
Next perhaps it would work to eval the entire expression.
Code:
while(($key,$value) = each %hash){
eval{
$string = s/$key/$value/g;
}
}
Then again, I'm terrible at doing evals, so if that works char for char, I'll be damned.
Either way, assuming the hash is the only way to go, I think an eval of some sort is your best bet.
I'm sorry I'm so unhelpful. You really picked one of the aspects of perl that I can't quite get a hold on. Hopefully someone can come along who's better at those than I am.