Relay + Arduino uses too much power for battery to handle. Which solution is best?
The TP4056 is a battery charger, not a voltage regulator. It cannot be used to supply power to a device like an Arduino. It is designed for charging the Lithium Ion battery from a 5V (e.g., USB) source.
By trying to use it as a power supply you're asking for trouble. It thinks it's trying to charge a battery (from a 3.7V nominal source) and will be doing things like:

Running constant current making the voltage fluctuate wildly as current demands change
Running constant voltage with limited current causing starving of power
Shutting off when it thinks it sees the non-existent battery being fully charged.

The TP4056 should be connected to a 5V USB power source and to the battery for charging it. The battery should be then through a (very) low-dropout regulator (ideally a switching regulator with zero dropout bypass ability) to power the Arduino at 3.3V.
Alternatively, if you don't need a (reasonably) precise 3.3V then you can power the Arduino directly from the battery.