Is there a remote, trustless bitcoin API that doesn't require anything (blockchain/SPV headers) to be stored locally?
The BOP Enterprise Bitcoin Server is an open source full node implementation with remote (that is client side) wallet. The server downloads the block chain does the transaction and block validation and routes transactions signed at the client.

The client connects to the server via a message bus. There is a Java and other APIs available with added client side features. Source code: https://github.com/bitsofproof/supernode

Commercial support and hosted instances available at http://bitsofproof.com