No meu sistema, que é o SQL 2008 (não o R2), o sqlcmd.exe está localizado em "C: \ Arquivos de Programas \ Microsoft SQL Server \ 100 \ Tools \ Binn". Se você estiver usando o R2, pode ser um caminho ligeiramente diferente. Você poderia tentar procurar "osql.exe". O osql.exe funciona basicamente como o sqlcmd, mas é anterior ao sqlcmd.exe e não é tão completo. No meu sistema, o osql.exe está no mesmo diretório Binn que o sqlcmd.exe.
Mesmo quando pretendo administrar o servidor remotamente, acho que instalar as ferramentas no servidor, junto com os serviços SQL, causa muito menos dor do que não instalá-las. E eu tenho usado o SQL Server por 12 anos. Certas coisas (como replicação) são muito difíceis de serem feitas manualmente ao se escrever Transact-sql porque as chamadas de stored procedures podem ser muito complexas, e muitas vezes falta algum utilitário aparentemente trivial que você precise precisar.