How can I check whether a username is in use?
You need add the condition for if the user exists or doesn't exist and then you are able to create two actions, depending on the user exists or not.

The problem is that this is not possible to do with Rules out of the box. It's not hard to add a condition like this, but it required custom code in a custom module. If this is not an option, what you are asking for is impossible AFAIK, as it doesn't exist.