All the participles in your examples are ambiguous between being verbs and adjectives. I will first explain why that is, and then I'll explain the concept of a participle.
For what it's worth: without further context, I personally would be more likely to interpret as adjectives all of them except the one in already tiring; that one is irredeemably ambiguous for me. Nevertheless, to repeat, all of them could be interpreted as either verbs or adjectives.
Verb vs adjective
Consider the following sentences (yours are  i a. and ii a. and  i and ii). As I will explain, tiring and tired are adjectives in iii and iv, verbs in v, and ambiguous between those two in i and ii. I will follow the discussion in various parts of CGEL.
 i a. He is tiring. b. He is dull. c. He is getting tired
ii a. He is already tiring. b. He is already dull. c. He is already getting tired.
iii a. He is very tiring. b. He is very dull. c. *He is very getting tired.
iv a. He becomes tiring. b. He becomes dull. c. *He becomes getting tired.
v a. He is tiring as we speak. b. *He is dull as we speak. c. He is getting tired as we speak.
 i He is tired.
ii He is already tired.
iii He is very tired.
iv He becomes tired.
v He is tired as we speak.
In  i a. and ii a., the ambiguity is between the verb to tire (in its intransitive meaning, which is to become tired) and the adjective tiring (which is applied to things that cause weariness and fatigue). For example, in the adjectival interpretation, He is already tiring means, roughly, 'He is already making everyone tired'. In contrast, in the verbal interpretation, it means exactly what  ii c. says: 'He is already getting tired'.
In  i and ii, the ambiguity is between the same verb, to tire (this time in its transitive meaning, which is to make someone tired) and the well-known adjective tired. Let's again look at ii. The adjectival interpretation is straightforward. To get the verbal meaning, it will help to attach a by phrase: He is already tired by all the attention, which is the passive voice construction whose basic counterpart is All the attention already tires him (we should imagine someone is giving a running commentary of what is happening, so that the present simple tense doesn't sound awkward).
In both  and , iii-v break the ambiguity by using constructions which are only compatible with adjectives (in iii and iv) or with verbs (in v).
In , the b. entries replace tiring by a word that is unambiguously an adjective, dull. The c. entries replace it by an unambiguously verbal expression, getting tired.
We see that both He is... and He is already... can work with either an adjective (in b.) or a verb (in c.).
However, only adjectives can be modified by very (and not even all of them, just the gradable ones). You can be very dull, but you can't *very enjoy it. This is why  iii b. is OK, but iiii c. is not.
Thus, the ability to be modified by very is sufficient grounds to conclude that something is an adjective. The converse is not true, however: just because something cannot be modified by very doesn't mean it's not an adjective (e.g. you cannot have *a very federal agency or *a very left exit).
Another distictive propoerty of adjectives is that they can serve as predicative complements (PCs). The most common verb that takes PCs is of course be, but that verb features in all kinds of other grammatical constructions where it takes verbs as complements, and it may be hard to decide whether one is looking at a PC or some other kind of complement. Luckily, there are other verbs that take PCs: seem, appear, look, become, etc. So you can appear dull, which is why  iv b. is OK, but you can't *appear getting tired, which is why iv c. is unacceptable.
Thus,  iii and iv can only have adjectival interpretations, with the meaning, roughly, he makes people very tired (in iii) or he seems to make people tired (in iv). Similarly,  iii and iv can only have adjectival interpretations, which probably don't need explaining.
Conversely, the adjunct as we speak normally cannot work with verb phrases of the form be + PC, which is why v b. is unacceptable, but it works perfectly with the present continuous tense, which is why v c. is fine. Therefore,  v a. only has verbal interpretation, whose meaning is precisely the same as that expressed by v c.
Similarly,  v only has a verbal interpretation, and again it will help to add a by phrase to get a better sense of its meaning: He is tired by all the heckling as we speak, whose active-voice counterpart is All the heckling tires him as we speak (we should again imagine someone is giving a running commentary of what is happening).
The concept of participle
From CGEL, p. 78:
The central idea in the traditional concept of participle is that it is a word formed from a verb base which functions as or like an adjective. A second general property of participles is that these words are also used in combination with an auxiliary to form a compound tense, aspect, mood, or voice.
The past participle
The adjective-like character of written is seen in .
 i I came across a letter written ten years ago. [head of clause]
ii He showed me a hurriedly written first draft. [attributive]
The most elementary type of noun-modifier is an adjective (as in a long letter, a careless draft), so written is like an adjective in that it heads an expression with the same noun-modifying function as an adjective. The secondary feature of forming compound tenses is illustrated in :
 i I have written him a long letter. [perfect]
ii The letter was written by her secretary. [passive]
Note that here, certainly in the perfect use in have written, there is nothing adjective-like about the form. It is its use in the perfect construction that provides the basis for the 'past' component of the name, for the perfect is a kind of past tense. No element of pastness applies to the passive use, but it is predominantly the passive that is involved in noun-modifying constructions like , which fit the central part of the definition of participle. 'Past participle' is therefore a reasonably good name for a form with the above spread of uses. It should be emphasised, however, that the inclusion of 'past' in the name does not imply that the past participle is itself a tensed form: it is a participle which occurs in construction with the past tense auxiliary have.
On p. 80:
This form covers the gerund and present participle of traditional grammar, which are always identical in form.
■ The traditional present participle
This has uses comparable to those of the past participle:
 i The train to Bath is now approaching Platform 3. [with progressive auxiliary]
ii The train approaching Platform 3 is the 11.10 to Bath. [head of clause]
iii He threw it in the path of an approaching train. [attributive]
Constructions [ii-iii] are those where the present participle is functionally comparable to an adjective in that it is head of an expression modifying a noun, and in [i] it combines with an auxiliary to form the progressive aspect. It is called the 'present' participle because the time associated with it is characteristically the same as that expressed or implied in the larger construction containing it (but see also §7). In [i] and [ii] the time of approaching is simultaneous with the time of speaking, but that is because the larger construction has present tense is. There would be no change in the form or meaning of if we changed to to give The train to Bath was approaching Platform 3. 'Present', therefore, is to be understood in a relative rather than absolute sense: the approaching is present relative to the time given in the larger construction. Again, however, it must be emphasised that the traditional present participle is not a tensed form of the verb.
On p. 81:
■ The traditional gerund
A gerund is traditionally understood as a word derived from a verb base which functions as or like a noun, as in:
 i Destroying the files was a serious mistake.
ii I regret destroying the files.
Destroying the files could be replaced by the destruction of the files, where destruction is clearly a noun. The primary difference between a gerund and a participle, therefore, is that while a participle is functionally comparable to an adjective, a gerund is functionally comparable to a noun. There is also a secondary difference: that gerunds do not combine with auxiliaries in the way that participles do.
And on pp. 82-83:
■ A distinction between gerund and present participle can't be sustained
Historically the gerund and present participle of traditional grammar have different sources, but in Modern English the forms are identical. No verb shows any difference in form in the constructions of  and , not even be. The historical difference is of no relevance to the analysis of the current inflectional system, and in accordance with
principle [5i] ['An inflectional distinction is accepted between two forms only if there is at least one lexeme with a stable contrast in realisation between those two forms'] we reject an analysis that has gerund and present participle as different forms syncretised throughout the class of verbs. We have therefore just one inflectional form of the verb marked by the -ing suffix; we label it with the compound term 'gerund-participle' for the verb-form, as there is no reason to give priority to one or other of the traditional terms. The compound term serves also to bring out the relationship between this form and the past participle: the gerund-participle has a considerably wider distribution than the past participle (which doesn't, for example, occur in constructions like [19i]), and yet the two forms have it in common that they head expressions modifying nouns, as in  and [14ii-iii].4 This grammar also takes the view that even from the point of view of syntax (as opposed to inflection) the distinction between gerund and present participle is not viable, and we will therefore also not talk of gerund and present participle constructions: we argue the case for this position in Ch. 14, §4.3.
In summary, words with a verb base and the -ing suffix fall into the following three classes:
 i She had witnessed the killing of the birds. [gerundial noun]
ii a. He was expelled for killing the birds. [gerund-participle form of verb]
b. They are entertaining the prime minister. [gerund-participle form of verb]
iii The show was entertaining. [participial adjective]