After configuring a new Raspberry Pi Zero W, I have not been able to ssh into it over WiFi. The IP address is assigned and pingable, but I get 'connection refused' errors.

After some research, I discovered one possible solution is to replace the SSH host keys on the pi.

But it's a Catch-22, because I can't login to the pi to change the keys that I need to change to be able to log into the pi.

What can I do?

Background detail: The way I configured my Pi's are as follows: Using Etcher.app on macOS, I flashed an SSD card with the full desktop version of Raspian, 2018-11-13-raspbian-stretch-full.img, downloaded from the Raspian site, and installed it on a Pi Zero W and a Pi 3B+, both headless, and used the headless approach to configuring WiFi and ssh (i.e. touched ssh in /boot and created wpa_supplicant.conf in /boot).

I didn't have this problem when I similarly installed Raspian lite (on my Pi 3B, about a month ago, 2018-10-09-raspbian-stretch-lite.img

At the moment I'm wondering if possibly installing the full Raspian on a headless Pi may thwart OpenSSH configuration (e.g. requires raspi-config to be run by user or something).

I will update this question if I find out the root cause to this, and whether the workaround is the best answer

Follow-up to @Milliway's comment below: This is the Reddit thread containing post that gave me the idea that regenerating host keys might fix the problem:

https://www.reddit.com/r/raspberry_pi/comments/704v5y/ssh_connection_refused_off_a_headless_setup/