Implement HTMLComboboxField. This is meant to be a replacement for HTMLSelectOrOtherField and HTMLAutoCompleteSelectField, but it would have a different interface, so I think it's a better idea to make it separate.
Browsers these days have surprisingly good support for <input list=...><datalist id=...>, which makes it possible to do this in plain HTML. As for OOjs UI, we have a ComboBoxWidget.