Consider the transformation described in section 6.2 of RFC4634 ("US Secure Hash Algorithms (SHA and HMAC-SHA)"). Given the message block M(i), and hence the message schedule W, as well as the output of the block function H(i), how hard should I expect computing H(i-1) to be?
Interestingly, the 64 "rounds" are easily reversible for this set of knowns and unknowns, but the final addition makes using this fact not trivial.
No, this 'unappend' operation is effectively infeasible for the SHA-256 hash compression operation; there is no known way that is less expensive than brute force.
Such an 'unappend' operation would reduce the time taken to generate preimages from $2^{256}$ to $2^{129}$ hash compression operations (assuming that the unappend operation is as cheap as the forward hash compression operation). This would be done via a meet-in-the-middle attack, where in the most straight-forward implementation, you generate one list of $2^{128}$ intermediate states (from $2^{128}$ prefixes), and you generate a second list of $2^{128}$ intermediate states (from $2^{128}$ postfixes; starting from the target hash, you use the unappend operation), and search for a common value in the two lists.
