So what do you suggest?
Paper wallets?
Multisig paper wallets maybe? (for extra security)
What would be a fail-proof solution in your guys opinion?
You are somewhat secure.
As long as all the devices are secure and you backup your HD seed or another wallet backup in another usb stick and store that in a secure location offsite and encrypted with a high entropy unique password than the only risk you may have is the original machine being compromised (unlikely as long as you took a few precautions) or you forget your passphrase.
This is where using either mutisig or Shamirs 2-of-3 Secret Sharing Scheme comes into play because it protects you from both physical theft, hardware failures, or you developing amnesia and forgetting the passphrase.
It is also a good idea to split up your balances so not all of it is saved in one device in case it gets exploited and all your private keys stolen in one transaction. With paperwallets this is easier done.
The idea of needing several pieces of paper (which you will have spread across the homes of different trusted persons like parents/brothers) is pretty stressing... you never know what would happen, you could still get in a fight with the so called trusted third parties and they could unintentionally lose the papers anyway.