While it's theoretically possible, it's not easy and it's a really bad idea.
The reason it's a bad idea is that you would effectively give the entire internet access to your server if only they figure out a username that does not already exist.
Still, here are three ways to make it work.
The easiest way is to have a script that is watching /var/log/auth.log and looking for failed logins, and when someone is trying to login to a non-existent user it'd create that user. This will require the user to try a second time in order to actually get access.
A second way would be to use a pam module to allow random users to login even when they don't exist. Or you could use kerberos, and setup a kerberos server that will answer positively to any login request regardless of the username.
A third way would be to rewrite the sshd source to create the user when someone tries to connect.
And I strongly advise you against using any of these ideas on any server connected to the internet.