If you know that TF changes are guaranteed to be deployed within X days of writing them (e.g., with something like Atlantis, or even a weekly deployment schedule), then you can put a date in the comment of when the tombstone was added, and clean it up either automatically after X days or occasionally in a semi-automated sweep.
But anyway, agreed, I think the stateful status quo is the way to go.
Not really. In every other system you can remove tombstones after a while.
Adding a tombstone for deletion, or a formerly-known-as tag for renames, is only "state" in the way that reserved tag numbers in protocol buffers are "state". It is a little annoying to have to do, and it creates clutter that you eventually have to go back and clean up, but neither of those is a dealbreaker, and in the meantime it solves the second-biggest problem with Terraform, which is the inscrutability of what it actually thinks it's doing when it comes up with a plan you don't expect. (The biggest problem is how ridiculously inexpressive HCL is as a language.)
Under the hood, the terraform file is just JSON, so sed, grep, jq etc can be used to manipulate it (as well as any other tools you'd care to write).