Not sure there is a right approach, you still need to access the server somehow and since the machine A is only access point for now, you still need to get it physically at least once as well as other n machines. So, why not to collect all pubkeys to the USB stick and move it to machine A to spread to the server's users' home .ssh config dirs?
Without USB stick there are some options also.
Var #1. Temporary enable password login on server from machine A. Generate keypairs and copy pubkeys to server from machines B, C, D, etc. just in normal way. Disable password login to server.
Var #2. If even temporary password login is considered as a security flaw, create a temporary user on server that has access nothing but its home directory, enable password login for this user only. Generate keypairs and copy pubkeys to server from machines B, C, D, etc. to this user's home directory. Pubkey is not a confidential and its potential hidjaking is considered to be a safe situation, however its spoofing is not, so you may consider encrypting or signing it somehow (gpg). Login to server from machine A, spread pubkey to server's users, disable the temporary user used.
Var #3. If the ssh server reboot is not an option, you could make machine A to be a temporary ssh server and use it as a intermediate station to copy ssh pubkeys to the real server.
Var #4. Use another communication channel (another remote server, maybe even public one, e-mail, etc.). Once again, pubkey is not a confidential, but make sure to sign them to protect from spoofing.