По бумажкам — вообще, требуется либо грамотный юрист, который составит договор на консультационные услуги (но это довольно опасная фигня), либо же ООО + лицензия на телематику (здесь мы уже от уголовной ответственности уходим) + сдача узла связи (без узла связи штраф 3000 рублей). Либо же можно работать абсолютно в черную, до сравнительно больших оборотов вы никому не будете интересны, особенно если сервера не в России.
По поводу софта — Возьмите реселлинг лучше у нормальной конторы, никакого геморроя, все на хостере. Если же хочется свое — VPS/VDS с 512+ (лучше 768-1024) Мб оперативки, панель (DirectAdmin, Cpanel, ISPManager, можете с Virtualmin поиграться). Плюс вам нужен будет биллинг и система поддержки, скорее всего.