I did some research earlier. The problem are linux-image-aws and linux-image-extra-aws packages. They don't have framebuffer driver in them.
Solution is to use linux-image-gke packages. Although you will lose AWS optimization (I heard it also makes your server a bit slow), but you will get framebuffer device.
To install them run apt install linux-image-4.4.0-1031-gke linux-image-extra-4.4.0-1031-gke.
Note: If you have both linux-image-4.4.0-1049-aws and linux-image-4.4.0-1031-gke installed, Linux will prefer linux-image-4.4.0-1049-aws because of higher version number. Make sure you purge those AWS packages after you installed GKE (Google Kubernetes Engine) packages.
Update for Ubuntu 18.04:
Things have changed a bit in Ubuntu 18.04. This will do the job now :)
sudo apt purge -y linux-image-aws linux-image-$(uname -r)
sudo apt install -y linux-image-gcp
sudo apt install -y linux-modules-extra-$(ls /boot/vmlinuz-4.15.0-*-gcp | grep -oP 'vmlinuz-\K.*'-gcp)
sudo apt-mark hold linux-image-gcp linux-image-$(ls /boot/vmlinuz-4.15.0-*-gcp | grep -oP 'vmlinuz-\K.*'-gcp) linux-modules-extra-$(ls /boot/vmlinuz-4.15.0-*-gcp | grep -oP 'vmlinuz-\K.*'-gcp)
sudo reboot