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.
Yes, the private keys are what actually needs to be cold stored etc. I used the term 'coin' just to make idea clear. For people who are unfamiliar with or new to Bitcoin, if I use the term 'private keys' instead of 'coins' then that may be difficult to understand.