How to power an Arduino using automated mains/rechargeable battery switching?
Yes, charging a battery and supplying an Arduino at the same time is possible as long as we manage the caveats (see below) of in-circuit charging.



This is what I use:


a 3.3V Arduino (a Pro Mini in my case),
a regular Li-Ion battery,
a charging controller that supports constant voltage (CV) and constant current (CC) charging,
optionally, a 6V solar panel.




This is how it works:


charger is fed via solar panel and/or USB supply,
battery is continuously supervised and charged on demand
Arduino is connected to the output side of the charger


This works because the load that the Arduino presents is relatively small compared to what the charger can feed (and what the battery can take). 
During recharging the charge current will predominantly flow through the battery. 
And since the current through the battery drops once it gets full, the charger can still recognise this drop and finish the charge cycle – even though the Arduino is connected all the time.



Example setup:

I took some quick snapshots, please excuse the image quality. Charger is in the center, Arduino to the upper left, battery in a holder to the lower left, solar panel to the upper right. 

The Arduino has a voltage regulator, but I don't use it in this setup. An explanation why and when to use the regulator is beyond the scope of this question and a matter for another answer.



In the first photo the charger input is only connected to the solar panel, but the panel voltage is low. So the charger is actually off and the Arduino is running off the battery.





In the second photo the charger is now connected to a USB power supply. The charger is on and in CC/CV charge mode (as indicated by the red LED of this charger model).





In the third photo the charge cycle is completed, the battery is full (as indicated by the blue LED of this charger model). Note that the charger could determine the charge completion even though the Arduino is connected and running (no power saving tricks involved here).



Background info:

The charger switches between CC and CV mode, depending on the level of discharge the battery is in. Particularly, my charger uses CC mode in case the voltage on the battery side is below 4V and CV mode in case the voltage on the battery side is above 4V. The current limit can be configured and the voltage limit is hard coded to around 4.2V, which makes the circuit save for a device like Arduino.



Image source: Nanjing Top Power

Other chargers may have other thresholds, but that doesn't matter as long as it fits your battery type and uses constant current/voltage only.
I have no particular recommendation for a charger, but so far have a good impression of the one I used in this answer.



Caveats:

There are a couple of cases to consider, though:

Deep discharge

Should the battery voltage ever go below around 2.9V (e.g. deeply discharged battery), the charger will switch into trickle charge mode where only very small amounts of current are passed to the battery – too little current (i.e. too low a voltage) for the Arduino to run. Arduino will go into brown-out and try to restart until the battery has recovered. So this can become a state in which your Arduino won't respond for an unknown amount of time.

High load

If the load connected to the battery draws a current that isn't small anymore – compared to the battery charge current – then the charger cannot recognise a full battery anymore, since the current as seen by the charger will never fall off at the end of any charge cycle. So watch out how many gadgets you connect to this kind of in-circuit charger.

Wrong charger type

There are a multitude of ways to charge a battery. Things like trickle charge, pulse charge, timer based charging, and so on. 
None of these would likely work, as the voltage those charger types generate could upset the Arduino and the load the Arduino presents could upset the charger.

Please also note that some chargers don't supervise the battery. With Li-Ion or Li-Poly (and other) batteries this would be a very bad idea. Always choose a charger appropriate for your battery.



Alternatives

The charger I use employs a linear regulator. That's not very efficient, other topologies are possible. But they might require supply filtering for the Arduino.



Shameless plug

I wrote a library for the purpose of supervising an Arduino's supply voltage (and chip temperature). This technique allows to check the battery level without any additional components. That library is called CoreSensors.



Further links:


New TP4056 Lithium Cell Charger Module with Battery Protection
Solar Pannel and LiOn or Lipo
How to autoregulate a TP4056 for maximum solar power extraction