Add options to multi-select with Javascript
Your best option would be to create a custom field type. That's quite a bit of work, though.

Failing that, you could add an extra "Other" option to the select field, and create a separate text field to hold the "free form" option.

Caveats

Craft isn't able to automatically validate the association between two fields. In other words, there's no such thing as "if the user selects the 'other' option, then she must also complete the 'Other' field".

If this is a must-have, you could implement some front-end validation, by injecting custom JavaScript into the Control Panel. Once again, a plugin is the best way to go here, but you may also be able to piggy-back on something like craft-cpjs, by Lindsey Diloreto.