How to exchange authentication keys
First, some notes on your choices of primitives:


AES-256: You don't need to use AES-256 unless the data you want to protect needs to remain confidential for more than 30 years
SHA-256 for authentication. Don't use plain SHA-256. Either use HMAC-SHA-256 using an encrypt-then-authenticate approach or (even better!) use AES-GCM or AES-EAX as your mode of choice as the two provide authenticated encryption (AE) and the likelihood of errors is much less.


Now to answer your questions:


If you store a key on both devices long-term-wise I think your questio means "How to securely transmit / negotiate a session key for authentication and encryption?". Well you could use ECDH to let both devices negotiate a key, but I assume this isn't possible in your case. In this case you simply generate a key at random, encrypt it using the long-term key and send it to the device, preferably using an AE mode, as you only have to manage one key then.
Who should generate a key? The one with access to the better randomness sources, usually this is the more powerful platform having more user interaction. (in your case the smartphone I think)
The answer on this depends on your situation. If the user-id is just some random number and if you're not too concerned with privacy of your users, you can send it in plain. If the user-id actually holds information (like a name) you could the connecting device send a nonce $N$ along with $Tag=H(N||ID||N)$. Then the device could try out all (4!) IDs and look for the match. This wouldn't expose the user-ids at any point in time in plain. If the user-id is low entropy and you want to protect it very hard, usage of a password hashing scheme (PHS, as function $H$ instead of SHA-256) may be an option to put more work effort to find the ID.
What you describe here is similar to the famous OTR protocol. To
perform the operation you need you'd simply use a key-based key derivation function (KBKDF/KDF) like HKDF. But be aware, as soon as the devices get out of sync (i.e. a message is lost), you'd need to renegotiate a new session. And note: using this approach doesn't provide forward-authenticity. Meaning if an old key get's stolen, all subsequent keys of the communication can be derived. In my eyes it's sufficient to use AES-GCM for the whole session and don't change with every message, as this means unneccessary performance overhead. You could simply renegotiate the connection every now and then to get a similar property.
Yes. Usually IVs are meant to be message-specific. This would result in you sending a new IV with every message. To avoid replay attacks you may also want to consider using message numbers.
If you do the setup as described at the beginning (using the password copied from the device to the phone) and you do already use authentication at this point, you're safe, assumed that the transmitted password wasn't intercepted, because an attacker can't fake the authentication tag. (excluding faking of the sender) He can't get the key on the receiving end, because this would mean he can decrypt the key, encrypted using the password which is impossible for any good password (random, 20 chars, lowercase, uppercase(, numbers))


I hope this answers your questions.