PLL versus putt-putt-skip, putt-putt-wait, fractional-rate division, or other approaches
These methods are used.  The TI MSP430, for example, uses something they call a "modulator" which is essentially what you're talking about.

The main advantage is that that they are super simple and they can change their output frequency quickly (without any lock-time or whatever that PLL's require), and without any "glitches".  

I'll also mention another method that you didn't mention (directly).  It is, essentially, a super simple version of making your approaches 3 and 4.  It's called a numerically controlled oscillator.  Here's a code snippet in VHDL (but it's generic enough that most should be able to follow):

signal phase :std_logic_vector (n_bits-1 downto 0) := (others=&gt;'0');

process (clk_in)
begin
  if rising_edge(clk_in) then
    phase &lt;= phase + inc;
  end if;
end process;

clk_out &lt;= phase(phase'high);


Basically, we have an n_bit long accumulator (a.k.a. counter).  On each clock, we add 'inc' to the accumulator.  The most-significant-bit of the accumulator is output as the new clock signal.  The output frequency is calculated like this:

Fout = Fclk_in * inc/(2^n_bits)


Where Fclk_in is the input clock frequency, inc is the value added to the accumulator, etc.  Fout can be anything less than Fclk/2.  For more accuracy, or a lower output frequency, you need more n_bits.  

The output of this logic is essentially a jittery clock, where the jitter is about 1 clk_in period.  The frequency and duty cycle will be dead-on (given n_bits and the clk_in period).  

I have frequently used this logic to generate baud rates and other slow but accurate clocks.  Since I work with FPGA's and not too many ASIC's I normally keep the logic synchronous with respect to clk_in and output a clock enable signal or something-- but the same concepts apply.