Can't upload media in any way

Hello,

I have started my first WordPress Page and came along an collection of errors that seems to be standart?

Anyway, I can’t upload media, it seems.
I have browsed the web (including this board), but nothing has helped so far. Not changing the chmod in the FTP to 777 or 766 or whatever all those were, not creating or deleting a uploads folder, not checking or unchecking the “create folders for year and month”.

When uploading via media:
via browser uploader:

Error saving media attachment.

via multi-uploader:

“XY.png” has failed to upload due to an error
Unable to create directory wp-content/uploads. Is its parent directory writable by the server

When uploading via “Add media” in the “New Post”:

Unable to create directory wp-content/uploads. Is its parent directory writable by the server?

When using the Multi-uploader while having checked the “Create year and month folder”, the message becomes:

“Ji-hoon_Paris.png” has failed to upload due to an error
Unable to create directory wp-content/uploads/2014/02. Is its parent directory writable by the server?

I have used chmod on contents, on a upload folder that I created (even though I heard, wordpress has to make that one itself, but it just doesn’t do so).
I had installed a old version of 2.something, same issues.
I even contacted my hoster, all he said was “777 for folders, 666 for files”.

I am at a total loss and I am loosing money, since I pay for a website that isn’t working (I can make a blog with it, but for that I might just as well have gotten a free blog from various providers)
HELP