Trute type fonts are fonts, not character encodings. UTF-8 is a character encoding set, not a font.
A font is needed to display the glyphs (characters) on screen, but it has nothing to do with the data stored. The characters need a specific character encoding to be stored, so that each character is mapped to a specific number (1-3 bytes in UTF-8).
As long as you are properly using character sets in PHP when performing the str replacement things should work ok as far as this is concerned.
Wether or not you have replaced anything, a font containing the proper glyphs is needed on the end users computer to display the text on screen.
Personally I'd recommend sticking to UTF-8 all the way. If you have a text which is not in UTF-8, start by converting it to utf-8 ([man]utf8_encode[/man] - only for converting iso-8859-1, [man]iconv[/man]). iconv is enabled by default, but your PHP installation might have it disabled if it was compiled with --without-iconv.
# first convert the text
$str = iconv('your charset', 'utf-8', $str);
# use an editor which let's you save documents as utf-8.
# That way you can type "special" characters directly into your document
# and save it that way
$str = str_replace('search', 'replace', $str);