Note: I had this happen with a recent download and install of Raspian full... it occurred on a headless pi zero W and a headless pi 3B+. This solved it in both cases. Not sure what was wrong with the keys but I suspect something may have been broken in the distribution.
If your ssh "connection refused" error is due to a problem with the Raspbian host's ssh keys (and one way to find out is to update them), you can replace them without booting into Raspbian if you have access to a running Linux host, which I will call a "helper" host.
Your Linux helper host could be Raspbian running on another Pi, Linux running on PC hardware, or if you only have a Windows or Mac host, it could be guest virtual machine running Linux with VirtualBox, etc... Assuming you have a way to mount the Raspbian media on that host, it's easy to reconfigure the SSH keys by simply overwriting them, because virtually all Linux distributions, (including Raspbian), have openssh installed, which offers the same set of tools.
HOW TO REPLACE SSH HOST KEYS ON RASPBIAN WITHOUT BOOTING INTO IT
Let's assume you've installed Raspbian on a 16GB micro SD card.
Put that micro SD into a USB flash card reader, and insert it into a USB port on your Linux helper host. If you're using a virtual guest you'll have to configure it to intercept the USB device (micro SD card reader), otherwise your host machine may snag that USB host and the VM won't see it.
On the Linux helper host, as root, run
fdisk -l
to find the device associated with your Raspbian media. In particular, you want to find the device associated with Raspbian Linux ext4 partition.
For example, in the following fdisk output the Linux partition is at /dev/sb2
$ sudo fdisk -l
Units: sectors of 1 * 512 = 512 bytes
Sector size (logical/physical): 512 bytes / 512 bytes
I/O size (minimum/optimal): 512 bytes / 512 bytes
Disklabel type: dos
Disk identifier: 0x989b1246
Device Boot Start End Sectors Size Id Type
/dev/sdb1 8192 98045 89854 43.9M c W95 FAT32 (LBA)
/dev/sdb2 98304 30375935 30277632 14.4G 83 Linux
Mount the Linux partition, as follows (we'll assume the device is /dev/sb2 and the mount point is /mnt through the rest of the example).
Note: Your actual device and chosen mount point may be different and you'll have to adjust this procedure accordingly.
$ sudo mount /dev/sb2 /mnt
Now you can generate new keys to replace the old keys in your micro SD's (Raspbian OS) ssh directory:
$ sudo ssh-keygen -f /mnt/etc/ssh/ssh_host_rsa_key -N '' -t rsa $ sudo ssh-keygen -f /mnt/etc/ssh/ssh_host_dsa_key -N '' -t dsa $ sudo ssh-keygen -f /mnt/etc/ssh/ssh_host_ecdsa_key -N '' -t ecdsa -b 521
Now eject the micro SD card, so you can safely physically remove it:
$ sudo eject /mnt
Note: Eject will fail if any terminal windows are still
cd'd
into any Raspbian partition directories, so either close any such windows orcd
to a different directory.