First of all, you should try using nomodeset (as you did).
Second, as Ubuntu (and Mint) are not really up-to-date compared to the new hardware, I suggest trying something in Arch Linux direction. The kernel used by Ubuntu is more than half a year old (with some fixes, but no major changes).
Third, you should NOT use AMD software from their homepage. The best you can do is adding a ppa (like Kisak's Mesa) for newer open source VGA drivers.
Fourth "Yes, AMD doesn't work. Nowhere on linux."
That's totally wrong. They are contributing a lot and the experience is really smooth in the past few years, but only with somewhat older hardware. What they really lack is to be able to have first day support, but after some waiting they won't disappoint you.