I agree that independent, decentralized verification would have to be in place for this to work...kinda like a separate block chain idea also mentioned here...people need some hope of gain to participate in verification...I guess a transaction fee lottery might work
I imagine also that redemption wouldn't require return of the physical bitbill-like card.
You could allow people to open the card and trade it openly on the p2p network - even in fractions.
A website could be setup which could see from the blockchain where all the fragments are. You could allow redemption of some minimum amount - so that if these were being traded around in fractions someone would have to accumulate a certain amount and spend back to your website to get the gold.
It would be risky to put these gold backed coins into a normal bitcoin client - as it'd be very easy to accidently spend them as input to an ordinary BTC transaction - but a modified client could track which coins were issued by you - and online wallet services could also implement this in cooperation with your site.