This can be created as a centralized service and migrated to a smart contract based solution afterwards. I am in the Plutus Pioneer Class so this will be easily done and fast in mainnet.

As a first solution create a Haskell service interfacing with dbsync and reminting tokens sent to it as described in the metadata. This will also have a small "pay by dust" component. The service in itself will run with two addresses, a payment address where the NFT holder sends their tokens and a burn address (which will be community generated) where the old NFTs get sent after they have been reminted.

Cost estimates:

Create DB Sync Haskell service with simple re-minting - 40hrs

Create and publish Smart Contract that replaces the DB-Sync service - 30hrs

Design and Implement Token Heritage Standard (followup proposal)

Cost Rate: 85€/hr

Total cost phase 1: 70 × 85 × 1.18 =7000$ (7021)