It means that the language allows side-effects; this is in contrast to pure functional languages like the lambda calculus, the pure subset of Lisp, or Haskell.
No, it means supporting changing the car and cdr of lisp lists, which allows creating cycles, which renders naive list walking functions useless, as they would cycle. length and every basic list operation needs to check for cycles.
And no, you don't do that with a naïve hash table, checking every cell if you already visited it. You do it with the https://en.m.wikipedia.org/wiki/Cycle_detection#Tortoise_and... algorithm, walking with two cursors ("fingers"), with different speeds.
Earlier simplier lisps didn't support rplacd and cycles and thus had much easier libraries and memory handling, but put strain on memory performance. This paper proves that destruction can be handled safely.
For all intents and purposes, there is no older Lisp that didn't have rplacd.
And, grandparent is right about what destructive means. It is not confined to assigning just to the fields of a cons cell, but to other things. Array elements, variables, slots of structures and so on.
How you deal with the possibility of cycles in the list structure in the library is simple: you don't. It's a complete waste of time for a list-processing function like, say, mapcar to be doing cycle detection. You document that it doesn't do that, and you will get infinite looping.
No Turing-complete language can save the programmer from infinite loops. If mapcar refuses to be goaded into infinitely looping, the programmer will find some other way to instigate non-termination.
