I know that that I can create a relationship between exiting nodes. But can I create nodes and relationship at the same time?
If by single query you mean in a single run, yes, it can be done. You can use the CREATE clause for creating two new nodes and a directed relationship between them:
CREATE (c1:City {name: "UK"}),
(c2:City {name: "London", population_size: 9000000})
(c1)<-[r:IN]-(c2)
RETURN c1, c2, r;