Program Arduino then Remove Atmega?
Yes. The programming of the arduino microcontroller sets the values inside the FLASH. This is non volatile memory and as such won't be erased by taking out the IC.

Please note that this is assuming a DIP package IC as these can be removed without force, heat and stress. A TQFP, and SMT packages like that, IC might get damaged by moving them in such a way. This doesn't mean it has to be erased, it is still non volatile storage, but the moving process is much more dangerous for the chip.

I would recommend connecting the whole arduino or if you really need the whole chip: designing your own board/circuit which allows you to program the chip without moving it around as this is really tedious and not worth the effort. Also moving the chip around is a ESD hazard.

Also please note that you'll need to add a clock source for the chip to work (most of the time). Or you'll need to enable an internal PLL. It will in any case require more effort on your part to make sure that the MCU can work. Therefore using the whole arduino board is preferable.