Yep, wrong algorithm. Yours runs in O(nm), where n and m are the length of each string - find_first_of is a linear search, and it will be particularly painful when there's no instance of a letter from str2 in str1.
Here's a linear-time approach :
To speed things up, keep a count of how many elements of str2_letter are still set and bail out early (don't forget to append the remaining characters from str1 to the end of str3). You might also play games to figure out which of str1 or str2 is shorter and have separate code for either case. Won't matter if they're similar size, but you might see an improvement if one is vastly larger than the other.
Create an array str2_letters[1<<CHAR_BITS], initialize to 0
For each letter in str2, set str2_letters[str2[i]] = 1
create temp string str3 = length of str1 + 1
for each letter in str1
if str2_letters for that letter is set
clear st2_letters at that index
append letter to str3
terminate str3 with a 0
optionally copy from str3 back into str1