Based on my understanding of your requirements, I am not aware of a published algorithm specifically for your case, but you can make one using the following discussion.
I will use an odd example, but you will see why soon.
Let us say you have a string such as
Character in position 3 can have values (1,2,3), that is 3 distinct values.
Character in position 5 can have values (4,5), that is 2 distinct values.
Character in position 7 can have values (6,7), that is 2 distinct values.
Possible outcomes of performing various replace operaiotns on the original string are shown below.
The total number of strings we can obtain is 3x2x2 = 12 (including the initial string).
This process is similar to generating Cartesian product of 3 sets (like SELECT * FROM T1, T2, T3).
Given a string length of N letters, if each letter i has at most r_i possible replacement characters, then we'd have a total of (r_0*r_1*r_2*...*r_N) words where r_i=1 if there are no replacements for the letter.
The reason I have choosen this specific example is that there is a description on how to generate the Cartisian product in here that uses similar values, so it would be easy for you to follow (although it is not in either Ruby or Python).
The concept will be the same if you map 1 input character to more than 1 character as long as make a single pass to the string and use the appropriate function to perform the replace.