How did I lock myself out of my server, and how did I fix it?

Story Disclaimer: Following guide helps only if you have phisycal access to the server, so you can obtain the storage device. If you don't (which often happen on cloud like AWS) and you don't have backup.. well there is nothing you can do. Yeah, so...