Changing the CSRF token with each request would work, but you also risk frustrating your users this way. If you have more than one tab open on the same web application, you could only submit a form successfully from the "freshest" of these.
Well, technically you don't need to invalidate the earlier CSRF tokens. Saving a big number of CSRF tokens per user would of course require quite a lot of storage, but maybe you could devise some "clever" scheme, e.g. token = "n" + sha(user_secret + "n"), which would be random enough for preventing BREACH, but easy enough to check.
Yes, that's what I mentioned in my post. However, the way I understand "Randomizing secrets per request", it means sending new, random secrets with every request (i.e. generating a new CSRF token for every request).