And I would like to have the coins stored safely on the block chain without me having to do cold storage myself or having to trust a third party storing the coins for me.
you do realise that coins are on the blockchain right? they never leave the blockchain.. EVER, the only thing you need to keep safe is the private key (imagine it as the password that proves your identity to do transactions.) the privkey is not "holding" bitcoins. so just look after your private keys securely away from a computer that can be malwared, hacked or lost in a computer crash/ accidental hard drive format.