This is a common conundrum and one general solution for it is called 2-phase commit. The TLDR; for that is to have each system first confirm that it has received a message and then after both parties confirm that are able to commit, all parties finalize their actions. This may bring more questions to mind as there's a sort of 'turtles all the way down' aspect to the problem. The article above is a good place to start if you want to have a deeper understanding of this approach.
If your queue and database can engage in such a transaction, that solution may be fully adequate for your needs. Unfortunately, I haven't found support for this to be widely supported between many platforms or at least not obviously so.
If you don't have the option to use 'real' 2-phase commits, the solution generally comes down to implementing retry logic, making your changes as atomic as possible, and falling back to a human in the case where a transaction is not in a clearly valid state.
In your scenario, one option would be to make two updates to the database each committed separately. The first is on receipt of the request as you have discussed. The second update would record the status of the API request based on its response. If it responds with an error which you know indicates that it is safe to retry, you can automate some number of retries. For those entries with no response, responses that do not indicate that it is safe to retry, or those that have exceeded the limit of retries, you then implement some sort of remediation workflow. That can be as simple as a scheduled query that checks for any transactions which are in an unknown state. Even with 2-phase commit, you will likely still need some sort of reconciliation process to ensure all transactions have been processed properly.