Проблема с кодировкой символов, не могу выводить в консоль на русском, как быть?
# -*- encoding: utf-8 -*-
from __future__ import print_function
Python 3.5.2
Будущее уже наступило.... Можно этот заголовок уже не добавлять. Это было актуально во времена python 2.x

Просто сохраните файл скрипта в кодировке utf-8 - и пользуйтесь....
PS: 
Проверил на 3.4.x в Ubuntu 14.04.6 LTS:
root@ubuntuServer:~# python3 --version
Python 3.4.3
root@ubuntuServer:~# cat /etc/issue
Ubuntu 14.04.6 LTS \n \l
root@ubuntuServer:~# python3 ./hello.py
Привет мир!
root@ubuntuServer:~# cat hello.py
print("Привет мир!")
root@ubuntuServer:~# file hello.py
hello.py: UTF-8 Unicode text

все работает
Если это сервер с Ubuntu Server 16, то она не поддерживает русский язык.
И питон > 3.5.3 придется ставить отдельно.
Можно попробовать исправить это, поставив расширения на язык.
По опыту, сам пробовал, забил, и взял сервер на 30 руб дороже с Ubuntu Server 20