Rechargable Li-Po battery to power Arduino through ICSP header?
I don't think this is necessarily safe. The Arduino Uno has two power supply options - USB and through the barrel jack. If the barrel jack is used, the USB power is disconnected through comparator U5A and Mosfet T1.
+5V is derived from either USB (directly) or from the barrel jack (via regulator U1).

Feeding +5v directly to the +5V lines would not 'trigger' the USB power shutoff. Whether this is an issue for the USB device feeding the Arduino or not I'm not sure but I wouldn't bet on it.

More information here (similar question): Arduino Uno R3: Directly supply regulated 5V to 5V pin?.

I'd suggest using a similar 'shut off' on the Lipo supply that shuts off the Lipo supply is the USB is connected (assuming you are using a charging circuit this should not necessarily prevent you from charging over USB).
Really what is boils down to is 'how do I build a USB powered Lipo charger / power supply'.

Another option would be to use a USB powered Lipo charger/booster board like Sparkfun's Power Cell - LiPo Charger/Booster. You'd basically power the Arduino using the board - using the board's USB power in stead of the Uno's USB port. As Sparkfun has all the schematics for the board on their website (https://www.sparkfun.com/products/11231) you could also re-use their design to 'integrate' if with your design.
Similarly, you can have a look at how the Arduino Fio (https://www.sparkfun.com/products/10116) does it - it has an integrated Lipo charger.

From what I can see, all these work the same way: use the USB +5v line to power the battery charging IC. Then connect the battery to the voltage regulator. It wouldn't be too hard to modify your Uno to work like this - just cut the USB +5V trace and basically drop the charger/lipo in there.