How can the blockchain be pruned?
If the blockchain is tamper-proof thus cannot be changed, how can the data be removed?
Please be as explicit as possible.
The blockchain itself cannot be pruned.
Each block is verified through hashing all its data and a random nonce to find a hash that has a certain number of leading zeroes. If you even removed a single little bit of data from a block, the resulting hash would be changed. As most likely the new hash would not fulfill the difficulty requirement, the proof of work would have been destroyed. You'd have to create a new block to take its place. Then however, you would also have to recreate all subsequent block, as the parent's hash (think of it as a fingerprint) is included in its children block, i.e. if you change the parent, the whole blockchain succeeding from it becomes invalid as well.
What can happen is that the database of verified transactions that Bitcoin-Qt clients store is pruned. So far, after verifying each block, full clients keep every transaction that has ever happened locally. Instead, you could only keep the transactions in your database of which the outputs have not been spent yet.
A block has two parts: a short header (metadata) and a (possibly large) payload containing the actual transactions. Header contains all the necessary data to validate the PoW and chain of headers since the genesis block header. Additionally, each header contains an authenticating value of its payload. SPV wallets sync very fast because they validate only headers and not the payload.
If a block contains transactions whose outputs have not been spent, then nodes must store that block to prove to another bootstrapping node that the UTXO set indeed contains a certain element. On the other hand, if all outputs generated in a block (say X) have been spent, than a node can discard block X and say to another bootstrapping node "all UTXO of block X have been spent, just validate header and move on".
This is a conservative approach. While a bootstrapping node cannot be fooled into accepting invalid UTXOs, we also cannot prove to that node that "all UTXO of block X have been spent" without exhibiting the actual payload.
Now the question may be: How do SPV nodes obtain and maintain an untampered UTXO set? See this answer for details.
It's been a few years, but I figured I'd add this, since it doesn't seem to be talked about a lot.
First, its important to note that block headers are sacrosanct; they are essential to verifying the blockchain.
However, much of the payload is no longer relevant, since the outputs they generated have already been spent.
It would be nice of they could be removed from the database, wouldn't it? The issue with that, though, is verifying the integrity of the block. If we lose a few transactions, how can we verify that the header's payload hash is right?
To solve this problem, the original Bitcoin paper proposes a solution based on the Merkle Tree.
This tree is constructed by taking a series, hashing every pair of elements, and then repeating the process to that new series.
As the original paper states, this can allow us to remove old transactions, and still be capable of verifying the leftover ones: