If I understand correctly:
You have a 256-bit master key $K0$
Generate a random 128-bit value $N0$ and set the last bit to 0
Generate a 256-bit keystream $K1$ using $E_{K0}(N0)$ || $E_{K0}(N0 \oplus 1)$
Generate a random 96-bit value $N1$
Using $K1$ as the key, and $N1$ as the nonce, encrypt your message with AES256-GCM, and authenticate $N0$ as associated data
Include $N0$ with the ciphertext
As you suggested, this should give a 127-bit effective nonce size for generation of the key $K1$, plus a 96-bit nonce size for the actual nonce, resulting in 16 byte ciphertext expansion, and minimal extra computation, but now with a $2^{-111.5}$ probability of a key/nonce pair reuse.
Because there are only $2^{127}$ possible keys, you may want to consider additional ciphertext expansion, and instead generate a 256-bit nonce $N0$, encrypting the whole thing with ECB or CBC to get $K1$.
Be aware, security proofs may include keeping the nonce $N0$ (effective state) of the PRNG secret, and here you are providing it as part of the ciphertext. I would do it like this:
You have a 256-bit master key $K0$
Generate a random 256-bit value $N0$
Generate 256-bit key $K1$ by hashing $N0$ with something like SHA-384
Generate a random 96-bit value $N1$ (optional)
Generate $S$ = $E_{K0}(N0)$
Using $K1$ as the key, and $N1$ as the nonce, encrypt your message with AES256-GCM, and authenticate $S$ as associated data
Include $S$ with the ciphertext
Encryption only requires a single hash iteration beyond the initial scheme, in addition to the ciphertext expansion from $S$. Decryption of the message requires decryption of $S$ followed by hashing to recover $K1$. In this scenario a GCM nonce $N1$ is not required to be generated, since you are using a new 256-bit key with each message you can use a fixed nonce. You could also get $N1$ from the unused remainder of the hash output. The GCM key is also protected by encrypting the state of the PRNG, which is now a random input to a hash function.
It is probably not insecure to do it your way, I just do not feel good about exposing $N0$ directly. If the system RNG has some problem, exposure of $N0$ (or even $N1$) could give an attacker information they could use against you in some way. Dual-EC is a good example.