The term "Directories" in a SharePoint site is deceptive. The 'directory' structure of a SharePoint webservice is a virtual structure that is located in the SharePoint databases. You need to identify what object in the SharePoint Object Model the 'directory' is for example: http://sharepoint.domain.com/dir is probably a SPSite, with in the site you can have a 'directories' that are SPFolders, SPLists, SPDocumentLibraries etc.
So if by "create directories that don't exist" you mean in the SharePoint site directory structure, you wont be able to do with the WebClient. You have two options: the Windows SharePoint Services Object Model, and the SharePoint Webservices.
The object model is certainly easier to use in my opinion but it will require you to run the app on the same server as your SharePoint server. The Webservices are a bit more work but it enables you to use them remotely.
You will need to identify what kind of object you are trying to add (e.g. SPFolder, SPSite, SPList, SPDocumentLibrary ect.).
There is ample documentation for using the object model located Here but if you want to use the webservices you will need to access them at the following locations:
Administration Service http://<server-url:port-number>/_vti_adm/admin.asmx
Alerts Service http://<server-url>/_vti_bin/alerts.asmx
Document Workspace Service http://<server-url>/_vti_bin/dws.asmx
Forms Service http://<server-url>/_vti_bin/forms.asmx
Imaging Service http://<server-url>/_vti_bin/imaging.asmx
List Data Retrieval Service http://<server-url>/_vti_bin/dspsts.asmx
Lists Service http://<server-url>/_vti_bin/lists.asmx
Meetings Service http://<server-url>/_vti_bin/meetings.asmx
Permissions Service http://<server-url>/_vti_bin/permissions.asmx
Site Data Service http://<server-url>/_vti_bin/sitedata.asmx
Site Service http://<server-url>/_vti_bin/sites.asmx
Users and Groups Service http://<server-url>/_vti_bin/usergroup.asmx
Versions Service http://<server-url>/_vti_bin/versions.asmx
Views Service http://<server-url>/_vti_bin/views.asmx
Web Part Pages Service http://<server-url>/_vti_bin/webpartpages.asmx
Webs Service http://<server-url>/_vti_bin/webs.asmx
I suggest looking into the Lists or Document Workspace Service services.
Hope that helps.