“Randomly derived” is not standard phrasing and I suspect that it isn't what the author meant to write. From context, what is necessary here is to have a distinct key for each message. This can be achieved either by randomly generating a key (I think that's what the author meant to write) or by deriving a key using a key derivation function with a unique input. The second possibility could be called “pseudorandomly deriving a unique key”, because a KDF should be indistinguishable from random if you don't know its secret input, but usually we just say “deriving”.
Since the problem to solve here is the absence of a unique input that's distinct for each message, deriving a key is unlikely to be possible. However, it could be possible if there is a unique input for each message, but it isn't a simple counter, rather it's some long string. With a KDF to derive a key, a unique input of any length is fine. But to derive an 8-byte nonce, a KDF doesn't help, because no matter how it's done, a randomly or pseudorandomly generated 8-byte strings has a $\approx 2^{-32}$ chance of colliding if you generate two of them, increasing as the number of messages increases.
If you derive a key from a password and a salt, that's a pseudorandomly derived key. From the same password and the same salt, you always get the same key. Never use a key that's derived from a password to encrypt actual data: if you ever want to change the password, you'd need to decrypt and re-encrypt the data. Instead, use K only to encrypt a master secret S. Then, on a password change, you only need to decrypt S and re-encrypt it with the new K. Although S can be the key that you use to encrypt data, I recommend adding another level of indirection: it gives you more flexibility. For each message or each conversation, use S as the secret input to an ordinary key derivation function (e.g. KDF1 or KDF2 or HKDF) with two public inputs: a public nonce which is sent with the message (or the first message in the conversation), and a version number which is initially 0 and which you'll increment if you ever want to use S for different things in the future. Once you have that per-message or per-conversation key L, it doesn't matter how it was generated. For each distinct L, if you use L for multiple messages, each needs to have a distinct nonce. If you have different keys L₁ and L₂, you can use the same nonce twice, once for each key.
