Make it trivially easy to install a "printer" to your service on Windows, Mac, and Linux desktops. If you play your cards right, you might be able to get Fedora and Ubentu to include you as a printer by default right out of the box.
Everything I'm about to propose can be done via the IPP protocol and the PPD files. Write some FOSS GUI tools, but keep what you are doing open and transparent so that other people can make your tools better and make better tools. If you do it right, and don't utterly marry the tools to your service, you can get your tools pulled into CUPS, OpenPrint, and the main distros, which will just increase your user base.
Partner with internet cafes and with small copy shops, via revenue sharing. They get a cut of the revenue for the prints the come out of one of their printers. Use geographic location data, etc, so that someone's print job comes out of a printer nearby that they can easily walk in and pick it up.
You are competing against FedExKinkos web print service, except that their system is closed source, proprietary, overengineered, and Windows only. Compete againt it's weaknesses and costs. You can do 80% of what they do, for less than 10% of the cost to operate.
Also interface to the postal system and package delivery services. Set up some printers near to some key USPS distribution centers. But don't marry yourself to the USPS. Since you are growing via low-barrier partnering, you'll be international faster than you can believe.
Internationalize everything. Or be ready to.
Build a bootable CD that runs on a small cheap junk PC, so that someone can buy a good printer, use a cheap PC, and their existing internet connection, and sign up as a partner very easily. Think towards building a cheap little appliance, similar to the existing network print server appliances, that do the same thing. (If you can get some hardware hackers to reprogram existing devices to do it, even better. For printers with ethernet and USB interfaces, something like the SLUG will be a good choice.)
Suggest that partners set up a printer on a cart kiosk, and show up at cons, conferences, geek events, unconferences, meetups, and so forth.
This isn't a billion dollar business. Don't try for VC money. Grow out of revenues, partnering, goodwill, and OSS buzz.