Я разобрался. Попробовал curl залить фото и оно таки залилось. Python не умеет из коробки Content-Type: multipart/form-data; слать, после установки нужной библиотеки все заработало.
Рабочий header для моего post запроса такой:
> User-Agent: curl/7.30.0
> Host: cs312918.vk.com
> Accept: */*
> Content-Length: 56798
> Expect: 100-continue
> Content-Type: multipart/form-data; boundary=----------------------------c16a5ea66209