E-mail рассылка с mailman на shared-хостинге — возможно?

Да, вполне реально. У меня на reg.ru mailman крутился на shared, но там жесткие лимиты на количество отправок в час — для небольшой рассылки норм, а если база большая, письма будут уходить медленно. Уточни у поддержки хостера их политику по массовым рассылкам, а то могут и за спам принять.