Do I have any alternative? Like, say, don't download the blockchain from the deadslow P2P network, but from some "trusted" place like blockexplorer?
Electrum is what you're looking for, then:
http://ecdsa.org/electrum/This is
awesome. I am not sure if I like the strange wallet generation and the fact that I can't import my own wallet.dat, but other than that, I really like this.
How does the paper-based wallet work? More exactly - I know I can check the balance on, say, block explorer, but how do I send the bitcoins to someone when I have the private key?