No, this is not safe.
You must not apply a voltage that exceeds Vcc or is lower than Gnd to any I/O pin without taking countermeasures. Standalone programmers almost universally have resistors (generally 2.2k ones) in series with the data pins, which is enough to limit the current to where it won't damage things when using 5v programmer on 3.3v device (in fact, most programmers that have both 3.3v and 5v modes always run at 5v, and switching the voltage just changes what it puts on the Vcc pin - but thanks to those resistors, the current injection would not damage the part; AVRs are generally rated for 1mA through the protection diodes), but when using ArduinoAsISP, you don't have these.
Not connecting external power and using a battery on the target is fine, as long as above is taken into account. Connecting external power and battery at the same time would not be okay (the battery would try to charge from the external power if external voltage was higher than the battery - but without any of the charge control circuitry, this would just damage the battery (and we all know how gracefully lithium batteries react to abuse. If the voltage of the external supply was lower, it would try to power that external supply; this would probably (but not necessarily) be damaging to something depending on the specific.
During ICSP programming, the chip is held in reset, so all pins are high-z. Put a pullup resistor on the CS line of any SPI devices, otherwise the CS line will float, and could (and probably would) go low during the programming process, leading to the SPI device thinking the programmer was talking to it and trying to respond, which would play havoc with everything.
Yes, a device which is not 5v tolerant will be damaged if you apply 5v to its SPI lines, regardless of whether they are high-z or not (they will have protection diodes, but the current that would flow without countermeasures like the series resistors noted above far exceeds what the protection diodes are rated for, and would burn them out; this in turn generally "blows" the pin - usually this results in the pin being near-shorted to Vcc or Gnd through the burned out diode and all functionality of the pin being lost.
My suggestion: Use a 3.3v arduino as ISP (like a 3.3v pro mini with 3.3v serial adapter), or order a USBAsp or USBTinyISP that runs at 3.3v or has a jumper to select 3.3v operation.