How can I destroy Possibility Storm?
It triggers whenever you cast a spell from your hand, no matter what kind of spell. This includes an instant or sorcery you might play to try to destroy it, as well as creatures. (Playing lands is not casting a spell - it's a special action you can do.)

So yes, it's difficult to destroy. Keeping it from ever reaching the battlefield by countering it is of course the easiest way. If you happen to have something on the battlefield with an ability that can destroy it, like a Keening Apparition that'll work too. Similarly, if you're lucky enough to have a spell with Flashback already in your graveyard like Ray of Revelation, you could use that - it's not cast from your hand, so it's not affected.

But otherwise, yes, you'll have to rely on luck - cast your spells, and hope you hit something good. Do note that you don't necessarily have to destroy it; you could well cast a vanilla 1/1 creature and luck into something enormous, and your opponent is just as dead if you kill them without being able to control what you cast!