C#, как зарегистрировать блок в GAC без GacUtil?

GacUtil не устанавливается при установке фреймворка, только при установке SDK - так что вы не можете гарантировать, что он будет на коробке, на которую вы устанавливаете.

Это не будет работать в вашем пакетном файле, но если вы разработали приложение самостоятельно, вы можете использовать метод GacInstall, описанный ниже:
http://msdn.microsoft.com/en-us/library/system.enterpriseservices.internal.publish.gacinstall.aspx

В качестве альтернативы я бы рекомендовал создать msi файл для развертывания приложения. Учебник здесь:
http://www.dreamincode.net/forums/topic/58021-deploying-a-c%23-application-visual-studio-setup-project/

Было бы нежелательно включать копию GacUtil.exe в ваш дистрибутив, поскольку он поставляется по другой лицензии, и вы, вероятно, не имеете права его распространять