We all know that applications of crypto primitives like to not think about the management of nonces, and initialization vectors and often prefer to just set them to random values. This sometimes leads to problems, when then IV is too short.
For example, in AES-GCM, the variable part of the IV is only 64 bits. If for each message we choose the IV randomly, we will start getting collisions after a $2^{32}$ messages; which is very insecure depending on the protocol.
Now a hacky way to roll our own crypto would be the following:
AES-GCM with extended-IV
First of all, we will stop using the normal IV part of the AES-GCM construction. Instead, for each message, we will mangle the key like this:
$$ K' = \text{KDF}(K || \text{nonce}) $$
where $K$ is the original key, $K'$ is the new key, and $\text{nonce}$ is a nonce that is long (say 256 bits) and randomly generated for each encryption; $\text{KDF}$ is assumed to be a properly domain-separated PRF that returns a new 256-bit value.
Now we encrypt our message using AES256-GCM with the new key. As mentioned, we set the IV to some kind of constant value. We transmit $\text{nonce}$ along with the ciphertext.
I would expect that, because collisions are possible in $K'$, this construction has only $\text{len}(K') = 128$ bits of security. However, I find it hard to reason about its security. The main question:
Could this scheme be used as an alternative for AES128-GCM, but with randomized nonces (similar to XSalsa20Poly1305)?
I mean hypothetically! I would not actually such a construction like that. I don't think that would make any sense.
Edit: As Poncho shows, this scheme is obviously not nonce-misuse resistant. I badly worded the question. I updated it.