В итоге, путем проб и ошибок получилось такое решение (оговорюсь, что решение можно сказать "на коленке", если кто-то предложит варианты, чтобы сделать его стабильным, то я буду за).

1. В конфиге openssl.cnf:
- в самом начале добавляем
openssl_conf = openssl_def
- в конце добавляем

[openssl_def]
engines = engine_section
[engine_section]
gost = gost_section
[gost_section]
engine_id = gost
default_algorithms = ALL

Проверяем, что все работает, командами:

openssl ciphers |tr ":" "\n" |grep GOST
openssl engine gost -t
openssl engine

2. Далее качаем исходники Python для сборки (проверено на версиях 2.7.8 и 2.7.9) и распаковываем, например:

wget https://www.python.org/ftp/python/2.7.9/Python-2.7.9.tgz

3. В исходниках открываем файлик Modules/_ssl.c и делаем следующее:
- ищем инклуды:

#include <openssl/x509.h>
#include <openssl/err.h>
#include <openssl/rand.h>

после них добавляем
#include <openssl/conf.h>
- ищем функцию init_ssl. В ней перед строчками

SSL_library_init();
SSL_load_error_strings();

вставляем
OPENSSL_config(NULL);

4. Собираем Python и проверяем работу с ГОСТ.