Have a look at the dijit.form.FilteringSelect widget. It's an alternative to a combo box.
By default it marks unmatched entries as an error, but it might be possible to disable that and allow values not in list.
As an alternative: check out the upload configuration page of Bildr (can be downloaded from OpenNTF). The "album" selection part allows you to select an existing album using a combobox. The combobox also has as entry called "New album" which displays an input field to enter a new album name not in the list already.