Nobody can build their own wallet directly from raw materials. Even in the very unlikely event that they had the know-how, they would still require highly specialised equipment manufactured by third parties. Therefore users of "crypto" have no option but to rely on goods and services provided by third parties just like everybody else. And the extent to which consumers can choose which parties to rely on (or "trust") depends entirely on the degree of competition in the market. Crypto isn't special with regards to trust. Calling it "trustless" is false advertising.
It’s not that hard to build your own wallet software, or if you really want, a paper wallet using dice and a pen.
But frankly it’s not that different than cryptography as a whole: nobody implements ECDSA themselves, or builds the computer that runs it, or smelt the metal and assemble transistors that runs the computer, or whatever. There is no such thing as “absolute lack of trust” but some protocols can be “less trust requiring” than others—e.g. more “trustless.”
Surprisingly, no. All a "wallet" has to do is compute a signature using a private key. Then the resulting transaction has to be sent to a "mining" node (or the "mempool" of a group of nodes) and wait until one of them incorporates it into a transaction, computes fourty trillion hashes and then throws all but one of them away, and broadcasts the resulting signed block to the network.
Because there is no confirmation on sending bitcoin "into" a wallet, no action is required at all to receive and store it. It's only cashing out where it gets difficult. It also makes it possible to send to inaccessible or nonexistant wallets.
Right, it doesn't interact directly with other wallets, but it has to interact with other parties using an electronic protocol in order to be useful. So a piece of paper isn't enough. Some kind of electronic machinery is required to build an actual cryptocurrency wallet.
Wallets tend to have two main features: A) generate random private keys and B) given some private key, sign a transaction and broadcast this message to the network.
Pen, paper, and some dice (and a bit of work) can generate a private key for step A, which you can input into a hardware wallet, and which would have prevented the problem in the OP.
It’s also possible to write your own wallet software or use a “trusted” tool (eg: openssl or node) to create a private key, rather than rely on a random app or device off eBay to generate it for you.
The B) part is harder to do with pen and paper or an off-the-shelf tool as it involves a fair bit of protocol specific math—but it’s also harder to target in a hardware wallet supply chain attack.
So clearly pen and paper doesn't work, since it isn't possible to sign a transaction and broadcast the message to the network using only a pen and a paper.
Writing a software wallet would involve using third-party compilers, operating systems and hardware, which means it isn't "trustless".
It doesn’t mean “you can perform some action without trusting anybody or anything at all.” Protocols, software, hardware, and even your environment will all require various degrees of trust.
From the interactions that I've had with many supporters of cryptocurrencies on Twitter and Reddit, I don't think that this a common understanding of the word "trustless" (which literally means "without trust", by the way) within this community.
Even if we take "trustless" to mean "not trusting a single, centralised party" it's not clear at all that blockchains are trustless or even that they're more trustless than other payments systems such as Visa. That's a question that can't be answered from abstract principles. It would need to be answered empirically.
Of course it will depend who you ask; but most Ethereum developers at least would probably agree that the word “trustless” shouldn’t be interpreted literally as “without trust” to the extent your comments suggest, just as “serverless” systems might still involve servers. Call it a misnomer; there’s plenty in the English language.
