Whatever analogy you end up using to express your frustration, instead of introducing it with “J’ai l’impression d' essayer …” (or even “C’est comme essayer …), another way to begin it would be by using “Autant essayer … ” ([I/YOU] Might just as well try …), which I think captures a bit better the notion that the task or idea is so utterly impossible that it’s not even worth trying.
That being said, I think your idea of catching smoke with hands is pretty good:
Je ne sais pas par où commencer. Autant essayer d’attraper de la
fumée avec les mains.
or borrowing from Peter Pan, you might consider:
Je ne sais pas par où commencer. Autant essayer d’attraper mon/son/ton
ombre.
In fact I think you could probably be understood, if not idiomatic, by using any recognized difficult/impossible task as an analogy, e.g.:
Je ne sais pas par où commencer. Autant essayer d’assécher l’océan.
Je ne sais pas par où commencer. Autant essayer de compter les étoiles
dans le ciel.