Sounds like you don't test your group policy changes in a lab first, eh?
Create a GPO with settings the "Configure Automatic Updates" setting in the "Windows Update" node of the "Windows Components" node of "Administrative Templates" set to "Disabled". As long as you haven't done something to disable periodic policy refresh, which happens every 90 to 120 minutes, by default, the clients will pick up the change w/o needing a reboot.
If you have disabled background policy refresh or if you can't wait, break out a copy of "psexec" and start running "gpupdate /force" on clients after you make the above change. (Blocking background policy refresh seems like a really bad idea...)
Blocking this at layer 3 is going to be difficult because the Windows Update service is DNS load-balanced. I don't know that you can easily get a list of IP addresses.
You might get by with creating DNS zones "windowsupdate.com" and "update.microsoft.com" in the DNS servers your clients use with no records in it. Clients with cached DNS lookup results will be unaffected.
Alternatively, break out a copy of "psexec" and execute a little script on each client to stop the "wuauserv" service and mark it "Disabled". That'll stop it, too.
You really should be using WSUS, BTW.
Assuming a list of computer names in "computers.txt" (which you can get by exporting the results of a "Find..." operation from Active Directory Users and Computers to a file and cleaning it up w/ Notepad):
for /f %%i in (computers.txt) do (
start sc \\%%i stop wuauserv
start sc \\%%i config wuauserv start= disabled
This is a persisent change to PCs, but you can undo it with "Services" settings in a GPO later.
With that many PCs, one would assume that they're broken down into many geographic areas. You should probably distribute running such a script across servers that are located in the geographic areas closest to groups of computers.
If you wanted to get fancy you could use
dsquery or Joe Richards' (http://www.joeware.net)
adfind to export the lists of computers from AD. (You could also export lists of computers out of DHCP servers using the Support Tool
dhcpcmd, if that was a better way to get geographic lists...)