The cryptographic primitive you are looking for are public key signatures. They do exactly what you have described, but I'll add few remarks to your points:
- Re 1: The first channel you use has to be secure in some sense so no attacker can not pretend to be the server in the first step already. An example for such a secure connection would carrying it via usb stick by yourself if the other side knows you as a person. Or if they are all software installations of your code you can embed the public key in the source code (assuming the software arrives at the client in a secure fashion). Regarding the key size: 256bit keys are very short for most public key signature schemes. For elliptic curve schemes 256bit is lower minimum, for RSA you now need keys with 2048bit.
- Re 4: The public key will have a lot of entropy (the technical term for "huge scope for randomness"), but non the less it is bad practice to reuse keys for several applications. Why don't you just transmit the (independently generated) passwords in the first step already?