Boa tarde Rodrigo!
Em meu entendimento não há a necessidade de emissão de NF para a circulação destas mercadorias, uma vez que o art. 29, inciso II, Livro VI do RICMS/RJ nos traz a seguinte redação:
Art. 29. O contribuinte emitirá Nota Fiscal, modelo 1 ou 1-A, Anexo I:
I - antes de iniciada a saída da mercadoria;
II - por ocasião do fornecimento de mercadoria pelo prestador de serviços de qualquer natureza, quando houver incidência do ICMS indicada em lei complementar;
Desta forma subentende-se que apenas a empresa prestadora de serviço que forneça materiais tributados pelo ICMS devem emitir nota fiscal para circulação das mercadorias, o que não é o caso de seu cliente, pois se bem entendi este deve estar enquadrado no item 7.10 (Limpeza, manutenção e conservação de vias e logradouros públicos, imóveis, chaminés, piscinas, parques, jardins e congêneres) da lista anexa a LC 116/2003, que em seu art. 1º, § 2º nos traz a seguinte redação:
§ 2o Ressalvadas as exceções expressas na lista anexa, os serviços nela mencionados não ficam sujeitos ao Imposto Sobre Operações Relativas à Circulação de Mercadorias e Prestações de Serviços de Transporte Interestadual e Intermunicipal e de Comunicação - ICMS, ainda que sua prestação envolva fornecimento de mercadorias.
Com relação a incidencia do ICMS sobre tais materiais, temos ainda o art. 2º, incisos IV e V, Livro I do RICMS/RJ:
Art. 2.º O imposto incide sobre:
...
IV - fornecimento de mercadorias com prestação de serviços não compreendidos na competência tributária dos municípios;
V - fornecimento de mercadorias com prestação de serviços sujeitos ao imposto sobre serviços, de competência dos municípios, quando a legislação aplicável expressamente o sujeitar à incidência do imposto estadual.
Espero ter colaborado.
Att,
Ericke