I'm comming from over a year on Arch Linux and the only thing bugging me is that I can't play some Youtube videos without FlashPlayer on Iceweasel.
Is this a Codec issue? I've installed at least 50 packages with codecs and none works.

This is an example of video I can't play: https://www.youtube.com/watch?v=lYaeRVMCqzY

Notes:

I don't want to install Chromium, I don't use anything from Google, be it products or services.
I don't want to install Flash as it's a major threat to security and privacy.
I tried Gnash, no results.

Regards.

Flash for Linux is stuck at version 11.2 and will never get any better. Normal Flash is about 14 or 15 now. Many sites will not work with 11.2 so you either have to use Chrome (regardless of it being a Google product) Chromium (Chromium is not a Google product it is a collaboration, Chrome is Google browser) with pepperflash installed via non-free (backports if you are using wheezy) or used HTML5 which Youtube offers for most videos but some are still flash videos and if you don't install an up to date flash somehow you are not going to see them.

There's a major difference between Arch and Debian in this regard, then, because on Arch I just installed Firefox and 99.99% of the videos I could find worked, with no Flash or other software needed besides plain Firefox. For the rest that didn't work I used to have an add-on called "Youtube Flash to HTML5" installed, but it's developer removed the add-on from Firefox. I installed "Youtube ALL HTML5" but this doesn't make all videos work.

Funny thing is that this video played now, so it's clearly random if it's going or not to play.

By the sound of your last sentence there isn't a difference between Arch and Debian but the issue is your own Debian setup. What version of Debian are you running? What version of Iceweasel (which is Firefox) are you running? Do you have NoScript or AdBlock installed?

Thanks. Hi, people, it's been a long time since I've posted on LQ - but this thread gave me the answer I needed.
I run openSUSE 13.1, and I can't play Flash vids in Firefox. If I'm on the actual YouTube page, the VLC YouTube extension works - but not to watch a vid on any other page unless the vid is in HTML5.
I use Chromium now, they have their own pepperflash which they update regularly.

Does you Debian system have gstreamer installed? (gstreamer0.10-ffmpeg) I do no know if it has any relevance to YouTube, since I cannot use it, but is worth asking. I see Arch's Firefox has gst-plugins-good listed as a dependency, which is a gstreamer package.

The video whose link you posted doesn't need flashplayer. On my setup it plays on Firefox 35.a01using HTML5. I have neither gstreamer0.10-ffmpeg nor gstreamer1.0-libav installed.
jdk

The vid works without Flash because it is in HTML5. I didn't grasp the language, is it Portuguese (sp?)?

Yes, it's Portuguese. Brazilian Portuguese to be exact.
jdk

Wrong thread