I really like Mr. Shiny's answer, and I almost just made this a comment there, but I suppose it deserves its own answer.
You can say that someone is engaged in a Herculean task. When used alone, the word herculean implies great strength, but an Herculean task connotes "requiring tremendous effort, strength, etc.", in reference to the seemingly impossible labors that were required of Hercules in Greek Mythology.
Because Hercules succeeded in his labors, this idiom wouldn't go quite as far as to say that the task is utterly impossible--only that you'd have to be on par with a demigod to accomplish it.
Update
Along the same lines, but with a stronger emphasis on failure, the American Heritage Cultural Dictionary has the following note on the definition for Sisyphus:
A difficult and futile endeavor may be called a “labor of Sisyphus” or a “Sisyphean task.”
Either of these phrases requires at least a cursory knowledge of Greek Mythology, so they may not be appropriate for your audience, but saying that someone is engaged in a Sisyphean task seems to match your criteria well.