Déchets or rebuts are not appropriate in such case; they are too pejorative meaning they are both "non recoverable".
Abîmés par la vie is idiomatic but I would prefer On a pas été gâtés par la vie.
You might also simply translate it by:
On a tous les deux vécu des moments douloureux.
After being informed damaged goods is actually strong and might be derogatory, here are some new suggestions:
On est tous les deux des accidentés de la vie
On a tous les deux été brisés / des cas désespérés / des cas sociaux.
In slang, that might also be:
On a été des cassos tous les deux.