What is the equivalent of a "Certificate of Destruction" when using a cloud-hosted database?
1) When we issue the ActiveResource::Base#destroy command on a record,
  is the data truly destroyed? 


Sure not.


  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?


Sure not.


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


No. Ask your cloud provider but 99.99% = no.


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


Full data layer encryption.  Tricky but possible.