If you represent the state as a Sparse Merkle tree, you definitely can update the state root purely using a witness, even if you’re storing a small part of the state. I implemented this here using a concept I call a “deep Sparse Merkle subtree”. Example usage here. You can store only a subset of the state tree, which you represent as a subtree, and recompute the state root of the entire tree by updating the subtree with witnesses. What I haven’t implemented yet is recomputing the root of the tree by updating the roots of the subtrees you’re not storing, but that’s doable.
Light clients that just want to participate in state data distribution don’t need to re-execute the transactions in the block to recompute the state root, if they just use witnesses from the new (already computed) state root, so I don’t think you need to assume that they have the EVM available. They can assume that new blocks and their new state roots are valid, and update their tree accordingly with witnesses.