Can the Edge explore 2 be updated by merely connecting it to my phone? So without use of a PC?

Yes, with Garmin Connect mobile app you can update device software. And you can update maps using plain USB device connection to any computer. 

In theory yes, but even the customer support know that it's very slow and don't recommend it.

The 1st upgrade after I bought it restarted downloading and failed again and again for about a week - and I left them close to each other for the nights. I had the same Linux only situation back then so the cable thing wasn't an option. At the end I got some old PC to make it work...

I don't know if they improved it since or it's a matter of luck but it does work nowadays. But it's way slower than on the watch, it can take the whole night or even multiple nights, and it only downloads the firmware update, timezones files, but not the maps as they are super huge.

Last couple updates took no more than 30 mins to push firmware from the phone to device but indeed this is very slow.

I update maps on my device quite regularly, see https://wiki.openstreetmap.org/wiki/OSM_Map_On_Garmin/Download for premade maps and details how to create your own from OSM data. Not all data in these lists is current, specially for single-country maps.