Replacing the occurence of the character in string
An easy way to generate all of the possible 0 and 1 combinations is to use binary numbers.

If there are 3 ?'s then the combinations of 0's and 1's will be all binary numbers from 0 to 2^3 - 1:

0:  000
1:  001
2:  010
3:  011
4:  100
5:  101
6:  110
7:  111


So all you need to do is count the number of question mark characters (N) and then count from 0 to 2^N - 1 to generate all the possible 0 and 1 combinations.

Also I notice that half of these strings will have a 0 in the first position, and half will have a 1. I wonder if this feature could be used to reduce the amount of iteration you need to do.