Tecnicamente não precisa de CNPJ (qualquer pessoa física pode fechar contrato de serviço, seja contratada ou contratante), mas a nota fiscal facilita bastante a contabilidade da empresa contratante. Dependendo do tamanho da empresa, o compliance pode barrar a contratação de pessoa física.
Se ter um CNPJ não for uma opção, dá pra fazer via RPA (Recibo de Pagamento a Autônomo), que recolhe tributos nela. Geralmente faz na Prefeitura da residência do contratado.