I don't think that could be accomplished without a custom Visual Studio workflow. I think what would happen is you do a check to see if the values is yes or no after the item is created. If it isn't, you'd write that value into the choice options so it's available for the next person to use. Along with that, you'd want to make sure that the value they entered doesn't already exist in the list.
The alternative would be to have a lookup list be your choice column and have an additional line of column be below that on the NewForm. The lookup list would have an Other (Please List Below) value and when a user selects Other and fills in their value in the text field, this value is then updated in the lookup list via a work flow.
This opens the door for variations and duplicate records. You could maybe turn on content approval on the lookup list to prevent this from happening.
If this doesn't make sense I can go into more detail.