You know your board design. If you are using an external clock source (oscillator, crystal, etc.), you know what the frequency is. If you have no external clock source, you know you need to use the internal 8MHz oscillator. If it is a brand new chip (i.e. never programmed) you know that the internal source is selected.
The simplest process is to write the fuse value for the clock source at a low speed (AFAIK there is no limit on how low a frequency you can program the device). Once you have programmed the fuse values, you now know for sure what clock source is being used - because you have just selected it. If you know the clock source, you know what frequency it is, and you can easily work out the fastest possible programming speed.
The AVR will use whatever clock source the fuses tell it to use - even when programming. If you program the fuse to use the internal oscillator, then after the next reset it will start using the internal oscillator. If you select an external clock source, then it will use the external clock source for everything, including programming.
In fact this is one of the problems people face. They program the fuses to use an external clock source, but then forget to apply one and wonder why they can't program any more. If your AVR is set to use an external source, you must apply an external source, even for programming (sorry, I just want to keep reiterating that point).
Third question (from comments)
No, you don't need to program the fuses twice. Once you have programmed the fuse, it is programmed. You can change it again if you want, but you don't need to program it twice to make it stick. However, what you do need to do is reset the IC. While in programming mode, if you change the fuses, the value is not updated until after the chip undergoes a reset (either from the reset pin, or a power-on reset).