In this post I wasn't looking for a replacement for a wallet, but for a block explorer - only with a little bit more privacy. If you use a block explorer, you also have to trust the provider of the service to deliver you the correct data. And of course the type of service I was thinking about should provide you all necessary data to check that, including blocks / block headers all the way down to the genesis block.
The actions that you describe mimics an SPV-type of implementation closely. Since you mention that you are looking for a service that provides you with all the blocks / block headers, then you can just enable txindex on your full node, which indexes the transactions and you can run a block explorer on top of that..
Ideally such a service should provide a web interface where you could enter the timeframe (e.g. you remember that you should have received a transaction between day X and day Y, so you would download all the blocks in-between). So the service provider doesn't have to know the exact blocks. Once the blocks are downloaded, you could then cut off the connection to the Internet and process the data offline via a JavaScript interface, e.g. searching for addresses and transactions. Or directly process it with command line tools or so.
That'll be exactly like how SPV works. You would be looking for a more resource-heavy SPV, which could work if there is a demand for it.
The reason why this would be more privacy friendly than a SPV wallet is of course that on the SPV wallet the block data are on the server and you query addresses/transactions (which are then known by the server), while in the service I was thinking of, the server would only known the blocks you're requesting. Indeed technically it would be similar to BIP 157/158, only presented in another way and with more data analysis features.
Yeah, I think generally the key issue here is resource tradeoffs. Indexing more blocks requires more resource, and it would probably start to look more like a full node after awhile. Anyhow, would it be better if we use a blockexplorer with Tor, but only query one address with one circuit? Since you are essentially linking each address to one circuit only, I assume it would leak practically no usable information?