Updating the secret key used for HMAC
Does your embedded device have access to a random input source and a bidirectional channel?

If not, then there will only ever be as much entropy on the chip as you put on it to begin with, so there's no purpose in updating the key.

If so, then just do an authenticated key exchange and generate a new shared symmetric key occasionally.  ECC is best for bandwidth starved devices and lattices are best for computation starved devices.