Somewhat random thoughts on the subject:
I think you will be fine if you just overclock it at 16MHz and 3.3V, as long as you are supplying the 3.3V at the VCC pin and not at the RAW pin. When you connect the USB connector to your PC or to a power supply, the MCU and anything attached to VCC will receive 5V, something to be aware of so you can prevent damage to stuff that is 3.3V only. People overclock these things all the time.
There is not an internal crystal. There may be an internal oscillator, and it may or may not be accurate enough to upload sketches using USB. I don't recommend using the internal oscillator because you have a crystal right there on the board that you could be using and it's a lot more accurate.
You can divide the 16MHz clock frequency by 2 in software. At the top of your sketch in the setup section this will set the frequency to 8MHz:
noInterrupts();
CLKPR = (1 << CLKPCE);
CLKPR = B00000001;
interrupts();
If you select the Sparkfun Pro Micro 8MHz board from the Tools, Board menu when you upload your sketch and your sketch includes the above code, it will run at the correct speed, and it will be running at 8MHz. The bootloader and your uploads of new sketches will still happen at 16MHz, but your sketch will run at 8MHz. You can check all this out by using the blink sketch and verify you have it blinking at the correct rate.
After you upload a sketch that has the clock divide code, you will have to press reset at the beginning of upload to update the sketch or upload a different sketch. This is because the code that runs in the background and helps with the auto reset will not be expecting the adjusted clock speed, so auto reset won't work to start the bootloader. Hey, there is no reset on the Pro Micro! Well add one, wire up a button to short RST to GND.
Everything you wanted to know about burning fuses in one tidy paragraph:
If you know how to burn a bootloader, you know just about enough to figure out how to change fuses. In the IDE preferences check the box show verbose output during upload. When you burn the bootloader, the avrdude command lines for setting the fuses and uploading the bootloader will be shown to you. Copy one of the lines that sets fuses into a notepad and alter it to just burn the fuse or fuses you want to burn, and remove the other command line options that do things like upload the bootloader hex file and erase the chip and other things you don't want. You can google avrdude to find what the various command line options do. You can google fuse calculator to find a handy online fuse calculator that will help you figure out fuse values. That info combined with the MCU data sheet will give you lots of good info. Fuses are programmed when they are set to 0, and unprogrammed when they are set to 1, so that may be the opposite of what you expect. You'll need to know how to combine the binary bits of the fuses into bytes, so a little bit of binary math or understanding are required, or you can use the online fuse calculators I mentioned. If you get sloppy with setting fuses, you could do something like unprogram the SPIEN fuse by accident, and that would disable any further ISP programming and brick your chip. The only recovery from that would be high voltage programming, which is difficult on an SMD processor, especially the QFN package on the Pro Micro. Something to be aware of. You don't need to change fuses to do any of the stuff in the first few paragraphs, but if you want to experiment with fuses anyway, now you know how to get started.
And finally one more random thought. There is no such thing as an Arduino Pro Micro. Pro Micro was made by Sparkfun and Arduino company was not involved, and Arduino company does not make that model. It does happen to work with the Arduino IDE anyway, if you add-on the necessary board definition from Sparkfun.