Storing them online is out of question. You need to store them offline, but not in the conventional way. This is what you can do - you can write down the password or private key in a piece of paper. After this is done, you can tear it to two equal parts and then store each of these pieces at different locations. Even if a thief gets hold of one piece, he won't be able to access your wallet, as it doesn't contain the complete pass phrase.