My paper was rejected following a lengthy delay during which an editor published a similar paper
I would suggest submitting your paper to a different journal, but as a counter to the charge that "it's already published in journal X," include the correspondence you had with journal X. 

This should alert a responsible editor to the fact that something wasn't right at the other journal, and may be willing to give your paper a fair shake.

I'd also consider lodging a complaint with the publisher of the journal. This sounds like an ethical lapse somewhere: another paper got published, but yours was out of scope?