I think both a list and a text field is a good compromise. The label already says 'location', not country, so having a text field next to the menu would make it clear that you're aware that the predefined list doesn't cover everything, and would make sense there. It would also let people whose country is in the list but who doesn't live in a 'state' or a 'city' add what's correct for them.

Add a "why isn't my location in the 'location' drop-down menu" FAQ and I think you'd have done the best you could.