AES with no SubByte - recover the key
where K depends only on the round keys (we can compute its exact expression) in order to solve a linear system, but it seems really grueling


Actually, it doesn't look bad at all; that's 128 linear equations in 128 variables (over $GF(2)$); Gaussian elimination should be able to give you an answer in $128^3 \approx. 2,000,000$ bit operations; hardly infeasible (and certainly easier than any fault attack).

The only tricky bit is that the 128 equations are likely not linearly independent (a random set of 128 $GF(2)$ linear equations over 128 variables is linearly independent circa 29% of the time); if they are not linearly independent, then there will be multiple solutions (or none at all); multiple solutions imply multiple keys that are all correct solutions; your Gaussian elimination code will need to deal with that situation.