You've got a lot of questions there, I'll try to answer a few, and set you on the way to finding the answers to the rest of them yourself.
First of all, you are going to need an external ICSP programmer. Examples include the simple parallel port version, or the more powerful USBtinyISP from ladyada.
The fuses are NOT set by the bootloader. The arduino "system"
burns the fuses at the same time as the bootloader, but the bootloader itself does not affect the fuses.
Here's some more info on fuses...
http://www.ladyada.net/learn/avr/fuses.htmlYou can use a fuse calculator on the web to determine what fuses you need for a 4MHz clock. Then you'll use avrdude and your external programmer to burn the correct fuses on your micro.
Here's ladyada's tutorial on avrdude...
http://www.ladyada.net/learn/avr/avrdude.htmlTo use a 4Mhz clock, you'll need to create a new entry in the Arduino's Tools->Board menu. This new entry will specify that you are using a 4Mhz clock, and adjust the timing to suit.
You'll then write your code using all the usual digitalWrite() commands. When you
compile your sektch, using the "play" button, the arduino IDE creates a compiled version of your sektch in machine-language, an intel-format .hex file.
Since you'll have no bootloader, you'll then use avrdude and your external programmer to upload the compiled sketch to your micro.