What service that lets you create records/data into an immutable database storage system that cannot be deleted? I'm not sure if this exists or not, but is there a database storage system that is immutable, whereby it cannot be erased or be altered without someone knowning? Use case would be for public data that should not be manipulated or erased at all. And if there are any modifications it would be known. Also the data would have to be redundantly stored to prevent data loss or deletion. 

Is there a service that lets you host any type of data/records in this decentralized manner?
While the specifics will depend on the database system itself this could be handled with pretty much any of the RDBMS platforms out there.  Permissions will pretty much handle what you want.  The process that puts the data in would need to have insert permissions and all other access would be select only.

As far as tracking the modifications - most of the vendors have some sort of auditing capabilities.  I am most familiar with Oracle and in that you can audit the activity of a user, activity on a specific table, or even any time a specific data modification statement (insert, update, delete) is executed.  Again this is vendor and version specific.

As a further protection - make sure to have good backups that can be used to restore to a specific point in time.  This will ensure that you can return the data to a specific state in case of an error or system failure of some type.