How to protect my arduino, while hotplugging its power supply and other related electronics
There's usually a number of scenarios that can cause hardware to go poof when you plug it in to a live system.  Most of them you have managed to identify, so I won't go into detail here.

Suffice it to say that creating hot-pluggable devices isn't as straight forward as you would at first guess.

There are two main critical things to consider when designing your system:


Suppression


Invest in TVS diodes to suppress ESD.  All the IO pins that connect to the outside world that will be liable to be disconnected or connected at any time should be protected by adequate suppression.  Any inputs should also ideally be tied to a default state with pullup or pulldown resistors so they aren't left floating.


Connector


The connector itself is pretty critical.  Hot-plug connectors typically have different pins of different lengths so that they connect in a specific pre-determined order.  Normally you want your ground and shield to connect first.  Then your power supplies, and finally your IO pins.  Doing it in any other order is asking for trouble - such things as back-powering through the IO pins if the supply hasn't been connected.

If you can't use a proper hot-plug connector then there are ways you can simulate it internally.  You can add hardware (buffers, reed relays, FETs, whatever, depending on your signals) which normally isolate the signals from the MCU, and only when the MCU is powered up and ready does it then activate the buffers to allow the signals through.  Of course, the buffers themselves have to be able to withstand any possible back-powering etc while the plug is being inserted.

One other small trick is to ensure that all your IO lines have a series resistor in them.  This limits the maximum current that can ever go in or out of a pin (at a specific voltage of course) to a level that is safe for the hardware.  470Ω - 1KΩ are good values.