How do I create a directory on remote host if it doesn't exist without ssh-ing in?

You can use rsync.

For example,

rsync -ave ssh fileToCopy ssh.myhost.net:/some/nonExisting/dirToCopyTO

Note about rsync:

rsync is utility software and network protocol for Unix which synchronizes files and directories from one location to another. It minimizes data transfer sizes by using delta encoding when appropriate using the rsync algorithm which is faster than other tools.

I assume you mean you don't want to interactively log in and create directories by hand, rather than that you want to avoid using ssh altogether, since you still need a password or public key with scp.

If using ssh non-interactively is acceptable, then you can stream your file using cat over ssh:

cat $1 | ssh $2 "mkdir $3;cat >> $3/$1"

where

$1 = filename 
$2 = user@server
$3 = dir_on_server

If the directory already exists, mkdir complains but the file is still copied over. The existing directory will not be overwritten. If the directory does not exist, mkdir will create it.

If you do a recursive scp (-r), it will copy directories as well. So if you create a directory of the name you desire on the remote host locally, copy the file into it, and then recursively copy, the directory will be created, with the file in it.

Kind of awkward, but it would do the job.