That first looks like a simple project. However, I would like to use as few
parts as possible. My question is:
is is realistic to have the clock, DTMF decoding and encoding tasks all done
by a PIC microcontroler?


Certainly. You've got 60 hz available, which gives you an extremely accurate
timebase (long term)
DTMF decoding might be workable on the pic, but why not use external DTMF
encoder/decoder
chips. That's what they do. :)    The phone interface, to do this right,
won't be real simple. If you take it
in logical blocks it will be easy, but not simple.

Intercept the line during active time, provide a constant current source
with about 50mA and 24V.
Dial tone isn't strictly needed, but you can generate it easily.
Grab the number, change what you want, loop the outside line, dial it, then
connect the fax, and drop out of the connect.
Watch line current into the fax to determine on/off hook status.

2 - The phone is temporarily disconnected from the phone line (with a
relay). But here, how can the dial
tone, busy tone, operator voice (etc..) be heard by the person (or fax,
modem) who makes the call.


You just reconnect after you dial, say 10-100ms. The fax does what it
usually does.  Ideally, you're only adding about 1-2 sec to the call, so it
shouldn't irritate the dialing timeouts.

For bonus points, Have your output DC polarity mimic the incoming line, so
as to avoid accidental disconnect or large
thump noises when you transfer.   Automatically detect tone or pulse dial
outside lines, and allow the fax to use both as well.
Speed up your tone dialing, It's possible to get about a 30% increase in
speed by doing something a little non-obvious with the dialing.
DO NOT shorten the tone bursts below 50mS that rarely works.

Very little pic problems here really, mostly phone problems :)
If you can find it, a copy of "Understanding Telephone Electronics" from
radio shack is about indespensible.
It's about the best book on this sort of thing that money can buy.