[Edit]Sorry about the duplicate; I couldn't delete it.[/Edit]
Please, please put the "HMAC" identifier first: `HMAC-SHA-256'.
I agree with Yarin.
Wouldn't that still allow a replay attack on the client (someone posing as the server)?
The secret is using a negotiated "nonce" and something of a "OTP" for each packet; using something as simple as a "time-based one time pad" makes "replaying" non-trivial without knowledge of the "PSK"/generator.
If you would like to allow for more security at the protocol level, you may instead optionally require a unique "PSK" or "symmetric key" for each client.
Client (AES-256-CBC):SID(HMAC-SHA-256(PSK, LFSR(NONCE), (NOW-EPOCH)/SLICES)): "Hello, I am USERNAME! My session token is `NONCE'."
Server (AES-256-CBC):(HMAC-SHA-256(PSK, LFSR(NONCE), (NOW-EPOCH)/SLICES) == SID): "How may I help you USERNAME?"
You may also follow the complete requirements of the relevant "RFC", but that may be overkill for this project.
I'd advise using a good cypher designed for streaming and seeking. (I hate to advertise on anyone's behalf, but I've had success with "Salsa20".) However, if you use the above strategy, your idea of simple encrypting each block with a fresh "IV" is valid. You don't then need to worry about replay--beyond "DOS"--on either side unless the "PSK" is compromised as the packet "HMAC" includes an "expiration date" of sorts which can't be adjusted without knowledge of the "PSK"; both sides discard packets with an invalid/"expired" "HMAC".
The problem is datagrams can be dropped [...] not allow any IV to be used twice.