Is it possible to enable Allow Fill-in option for Lookup type columns, like Choice type columns.
As far as I know, there is no such functionality out of the box.
Overver, there is a codeplex solution that implements that. SharePoint 2010 Autocomplete Lookup Field (made by the user Nadeem Yousuf) - it implements a custom field type that adds autocomplete functionality to the lookup. You can have a look at it.
You can do it with Managed Metadata columns if the term set is defined as Open, and you set it on the column.