Most PICs are rated to being able to source up to 20mA and to sink up
    to 25mA at any pin. I understand that this is an Absolute Maximum
    Rating that one cannot stress.

    Now, keeping into the safe side, say that I want to source 15mA from
    ALL output pins of a 16F84. ... Ok, so far so good, one cannot do
    that. So the question is: How do I compute the maximum current a given
    chip can source at a time?

You don't have to compute it - it's already in the spec sheet.  In the same
"absolute max ratings" section, there are:

        Max output current sourced by a single I/O PORT 40mA
        "    "          "  sinked       "       "       50mA
        Max current out of Gnd pin                      150mA
        Max current into V+ pin                         50mA

(remembering someone odd ideas about current flow direction, all the
current "sunk" by IO pins should be coming out of the Gnd pin...)

BillW