Moving ATMEGA to 3.3V
...I have read that on low voltage I have to use 8Mhz crytstal...


Technically you can run anywhere below 13Mhz or so, so you have lots of choice.

You may also be able to use the prescaler to divide the clock by 2, either by hoping the ATmega can run the short time at 16MHz, or by programming the CKDIV8 fuse to start it at 2MHz.


  ...do I have to take the chip out to reflash with the programmer again...


If you move to a frequency within spec with either a clock change or prescaler use, yes. The bootloader and Arduino libraries expect a 16MHz clock, so you will have to rebuild the bootloader with the new clock rate, and sketches that use delay() et alia as well as the intrinsic delay functions will also need to be rebuilt.


  What will happen if I do not change the oscillator and leave it on 16MHZ ceramic?


It may work, it may not.