DavidC,
I am not sure I understand what the aversion to slicing and dicing is.

$str = join '', map $codewheel{$_}, split //, $str;
[download]

If you think that this is terribly inefficient then there is likely more to the story than what you have described. Looking at the whole problem might result in a more desireable solution. Otherwise, avoiding a straight forward approach just because you want to sounds silly.