Словарь русских фамилий - новиченко

Возможно два объяснения фамилии.

1. От слова новичок, возможно прозвище переселенца, нового жителя деревни. Есть же фамилии Новый, Новых. 

2. Более вероятно, от имени Новичко, производной формы от Новик (фамилия Новиков). В 'Ономастиконе' С.Б. Веселовского есть 'Новичко и Новиша, крестьяне, XVI в., Новгород'. Новичихин. От Новичиха жена Новика, Новичка. Фамилию по имени матери мог получить ребенок, воспитывавшийся без отца. Новиченко украинский вариант той же фамилии. В 'Ономастиконе' Веселовского Новиков Семен Меркулович, середина XVI в , Кашира и Рязань; от него — Новиковы; Иван Андреевич, 1627 г , Коломна Новик — вновь поверстанный на службу парень; Новичко и Новиша, крестьяне, XVI в., Новгород .