How about the standard solution, WPS. Depending on the method used, it does not require any UI-parts from the device (PIN or NFC methods) or just a simple push-button.
Electric Imp seems like a great solution (flash setup data from a smartphone to a light receiver on the device) but I wonder how they handle imposters. For example they brag about a connected door lock. If I was a bad guy I would go to the nearest window, and shine a bright light with the setup pattern through it hopefully reconfiguring the lock.<p>If they make it too hard to reconfigure the lock then it will increase the support load.
I've had a half baked idea about this for a few years. The thermostat has a terrible screen and is immobile, while my phone is the exact opposite. With Bluetooth LE, and perhaps NFC, you could make a configuration/maintenance interface that allowed for better setting management, using the phone as an interface.
Very interested in this space; for a screenless device it seems to me that 'act as hotspot' and 'usb to pc' are the only real sensible options, although they are not exactly ideal.
A hot-spot is a bad idea because most computers can't connect to two wifi networks at once. That means any time you wanted to configure your thermostat, you'd have to disconnect from the internet.