The idea I've employed here is to use a positive zero-width lookahead assertion to ensure that a match can only occur if there is one more character following the tilde.

$output =~ s/\x7E(?=.)/\x7D\x5E/g;
[download]

It could also be expressed without the zero-width assertion like this:
$output =~ s/\x7E\G(.)/\x7D\x5E$1/g;
But the latter will probably run slower because it requires capturing parens.

Update: Use the solutions with lookahead (Enlil's, duff's, or mine); they work, whereas the method that I've "crossed out" skips occurrences of the tilde if they're contiguous.