What is the equivalent of a “Certificate of Destruction” when using a cloud-hosted database?

Question

We have a Rails application hosted by Heroku and using an Heroku Postgres database. Some of the information we store is considered to be sensitive by our users, and we've been asked if we can provide a Certificate of Destruction in the event they wish to delete their account. In other fields (e.g. law) CODs are apparently common practice, issued for instance after sensitive paper documents are shredded or otherwise destroyed.

So I have three questions:

1) When we issue the ActiveResource::Base#destroy command on a record, is the data truly destroyed? We keep backup snapshots with Heroku's PG Backups, so even if the original command truly destroys the data, its probably still in the backups. Without deleting the backups, is it even possible to destroy completely the client's data?

2) Is there an equivalent to a Certificate of Destruction for this purpose?

3) If there is not an equivalent, how have other people mitigated or otherwise assuaged similar client concerns?