Нечитаемые символы появляются из-за мультибайтовости кириллических символов. Обращение к строке по индексу возвращает значение 1 байта. Кириллические буквы занимают по 2 байта.
Можно разбивать строку в массив по символам, используя разделитель, понимающий Unicode:
function _replace(&$str, &$trans){
$arr = preg_split('//u', $str, null, PREG_SPLIT_NO_EMPTY);
for ($i = 0; $i < count($arr); $i++) {
if( isset($trans[$arr[$i]]) && rand(0,1)) {
$arr[$i] = $trans[$arr[$i]];
}
}
$str = implode('', $arr);
}
Как бить, с учётом Unicode, взял
отсюда.