You can't deploy this without access to the GAC libraries, which are installed as part of ArcGIS Desktop or ArcGIS Server for .NET; there is no way of deploying an ArcObjects toolkit without first installing the above.
We deployed it with all it's library files contained in the deployment. This worked, but was completely at odds with ESRI licensing.
So in short, you can't do it without AGD or AGS 10 installed.
One other thing to note, regardless, and a major difference betwen 9.3.1 and 10, is that Once your tool model runs correctly, the tool needs to registered with the ESRI component categories before it can run within an ArcGIS Server 10 instance.
We have done this registration by creating a C# .Net setup project within our base C# .NET solution. This project has changed completely as a result of differences in component category registration functionality between ArcGIS 9.3.1 and ArcGIS 10 products.
Esri recommend placing common component category registration functionality in a separate C# .NET project that produces a DLL. This common DLL is then included within each setup project that needs it.
nerdy:
In ArcGIS 9 you used to register custom components with the ESRI component categories using the Windows registry. That's all gone and you do it via the 'InvokeEsriRegAsm'. It's the ESRI way of hooking the assembly in with COM without polluting the registry
E.g. Example of what I mean : ESRIRegAsmtility
Best Answer
The Services division at Latitude Geographics does ArcGIS Server hosting, but I have no idea what the cost is nor have I used it. I have used their Geocortex Essentials line and worked with them on custom ArcGIS Server web app development, and they are a great company with very talented developers, product managers, project managers - you name it. Give them a call, I'm sure they'd be happy to talk to you about options.