Of these various titles, the most widely-attested appellation for Jesus is that of the "Christ" and we can therefore probably presume that it was applied to Jesus almost immediately after his crucifixion, if not before. The word "Christ" is derived from the Greek word christos which means "anointed one" and is a translation of the Hebrew word mashiach (anglicised as "messiah"), which means the same thing. Now exactly how we should interpret this term in the context of early Christianity is a matter for debate, in part because the meaning of the word (or at least how it is used) seems to have changed throughout the history of Judaism. In the Old Testament, the term is used almost exclusively in relation to the divine appointment of kings and high-priests in Israel, who were literally "anointed" with oil as part of a religious ritual. David, for this reason, is seen as the first Messiah (see 1 Sam 16:12-13; 2 Sam 23:1), and it seems to have been used in this early period as a title to affirm the divine sanction of Judahite kings. Later, in the post-exile period when the royal house of David failed to be re-established, the term was applied more generally to other offices, including that of the high-priest (Zech. 4:14), prophets (Isa. 61:1) and even the Persian king Cyrus (Isaiah 45:1). There are then signs in the prophetic OT literature that there was a general expectation among the Israelites for the re-establishment of the Davidic royal line at some point in the undefined future (a new "Messiah"), but these expectations have of course not been realised.
A re-emergence of interest in Messianic theology emerged in the 2nd and 1st centuries BCE, doubtless partly inspired by the first independent (though non-Davidic) Jewish royal-line to emerge in Israel for over 400 years. The Hasmoneans ruled from 140-37 BCE and during this time (that we may crudely term the "inter-testamental" period) Messianic expectations of prophetic literature were revived, fueling a lasting belief that eventually one from the line of David would ascend to power in Israel and institute a golden age of peace and prosperity. This was also a period of enhanced eschatological speculation, which centred not merely on a historical epoch shift initiated by the Messianic claimant, but by the direct intervention of God. Although these themes would come to be woven together in early Christianity, it should be pointed out that Messianic expectations and eschatological expectations were largely kept separate in Judaism. However, we do find that many of the Jewish beliefs of this time appear to anticipate early Christian theology, for instance the idea that the Messiah would be killed as a preface to a general, universal resurrection of the dead (4 Enoch 7:28-34 and 2 Baruch 30:1) which is similar to the eschatology advocated by Paul in his early letters (e.g. 1 Thess 4:13-16) and elsewhere in the NT (e.g. Mt 27:52). Other Jewish literature from this period perceives the Messiah as a powerful figure, coming to rule in judgement over Jew and Gentile alike (Psalms of Solomon 17:23-35), perhaps sitting on a divine throne at the right-hand of God (see 1 Enoch, esp. 48:10 and 52:4) themes that also appear to have had some influence on the trajectory of Christian thought.
Such Messianic expectations took on a more practical importance during the 1st century CE, when there were apparently several claimants to the kingship during the first Jewish revolt (66-74 CE) and the second revolt, where the military leader Bar Kochba was explicitly hailed as the Davidic Messiah (132-135 CE). Luke even appears to suggest that the Messiah question was alive during Jesus' lifetime and was being applied to other individuals (Lk 3:15). Such facts tell us that the "Messiah" question was alive and well both immediately before, during and after the ministry of Jesus, though the earliest Christians appeared to envisage a more eschatological Messiah (see the numerous "Son of Man" passages in the gospels) than a political or military one. So anyway, what can all this tell us about Jesus?
In the first place, we must ask to what extent these Messianic "expectations" in Judaism may have affected how the early Christians viewed the significance of Jesus' ministry, and also - perhaps - how Jesus himself may have viewed it. Most scholars now accept that we can't draw a direct path from these heterogeneous Judaisms to the emergence of Christianity, and would also accept that simply pointing to Jewish Messianic expectations at the time of Jesus (as I have just done) tells us little about what the first Christians thought specifically about Jesus. Did they view him as a royal heir to David's throne, for instance? From the desire of NT authors to place Jesus into the Davidic genealogy (Rom 1:3; Mt 1:1-17; Lk 3:23-38) we can probably say yes. Such a perception may also explain (presuming the gospels' reliability on this point) the reason why Jesus was crucified under the ironic epithet of "King of the Jews" (Mk 15:26 etc.). That is, Jesus may well have been hailed as a Messiah in the traditional mould (as one claiming a particular political office) and this may have been why he was viewed as such a threat by the Romans.
But the traditional understanding of the word "Messiah" apparently does not exhaust the understanding the early Christians had about the term, as whatever royal claims were made of Jesus during his life, they were plainly never realised by any conventional meaning of the term. Nor were the hopes that the enemies of the Israelites would be smashed, either through divine retribution upon the death of the Messiah, or by the armies of the Messiah himself. However, we should note that whatever hopes Jesus may have failed to realise, this apparently was not cause for wide consternation among the early Christians: that is, rarely in the early writings are these failed expectations (or how they should be adjusted in view of this) ever raised. They were able to adapt the meaning of the word "Christ" into something new, something better adapted to the circumstances they now faced.
So within the first 20 years of Christianity Jesus had undoubtedly come to be considered "the Messiah / Christ", though probably not the kind of Messiah we can unambiguously identify in either the OT or the inter-testamental literature. Whether or not Jesus would have personally accepted this title during his own life is a little dubious: he is presented with many opportunities to affirm his status as the Christ in the synoptic gospels, yet only once is he depicted as doing so (Mk 14:62). Even then this account must be considered problematic from a historical perspective because this affirmation was supposedly given in a private audience before the Jewish high-priest (and who would have been present to witness such a conversation?), the "I am" is used as a springboard for Jesus to relay his "Son of Man" eschatology (which may be at odds with Messianic claims?) and the parallel accounts in Luke and Matthew (Mt 26:64; Lk 22:70) have Jesus giving a much more ambiguous and cryptic response. So, even by the testimony of the gospels, if Jesus was ever considered the Messiah during his own life, it was apparently a title that he was not keen to publicly embrace or advertise. In any case, we can probably suggest that the idea that Jesus ever considered himself as heir to the Davidic throne runs counter to our understanding of his teachings which express (at best) a deep ambivalence towards institutional power, and his eschatological beliefs that the powerful would suffer in the coming Kingdom of God and that it was better, therefore, to approach the kingdom like a child or a slave (that is to say, as one completely devoid of power) rather than as a king.
Other Christological titles are even more problematic. Probably the next most common title applied to Jesus in the NT is that of "Son of God", though again this is a phrase that can be interpreted in a number of ways. We know that such a title was used in Judiasm under a variety of circumstances, as I have previously explored on this blog:
Our understanding of the phrase "son of god" is unfortunately clouded by its rather literal use in gMatthew and gLuke, where Jesus' mother is impregnated by the Holy Spirit (Mt. 1:18, Lk. 1:26-35) making Jesus quite literally "God's son". However, this understanding of the phrase "son of god" occurs nowhere else in the New Testament and so we should not assume that the phrase means the same thing for Mark as it does for Matthew and Luke. Indeed, although the phrase "son of god" is often used in the New Testament as a unique title for Jesus (i.e. "the Son of God") it is a phrase with a long history and a wide variety of meanings.
In the original Hebrew of the Old Testament, for instance, the expression "sons of god" can be used to describe angels (or "heavenly beings" as it is rendered in many English translations - see Gen. 6:1-4 and Job 1:6) or holy men blessed by god (i.e. priests and kings, especially of the Davidic line – e.g. II Sam 7:14, Ps. 2:7; 89:26). The Jewish author Philo, writing in the same century as Jesus, used the expression "sons of God" in a very general way to refer to the entire Jewish people. And the expression doesn't only have a history within the Jewish faith: the Roman emperor Augustus (who was almost certainly emperor during Jesus' lifetime), for instance, was also given the title "Son of God" (from divi filius in Latin) during his long reign.
Yet even if we interpret this title as implying that Jesus was "[the only-begotten] Son of God" rather than merely "[a] son of God", the issue doesn't end there, as the exact nature of this "sonship" was a matter of often quite vitriolic debate during the first few hundred years of Christianity. The contemporary Christian understanding of Jesus as the pre-existing, "only-begotten" Son of God, descended from heaven, was of course the view that won out in the fallout from these debates, but there were other competing claims, such as those held by the "adoptionists". Such Christians held to the idea that Jesus only became God's son at the moment of his baptism at the beginning of his ministry, as Paul (Rom 1:4) and the Gospel of Mark (Mk 1:10-11, referencing Ps 2:7) may appear to imply. As for Jesus' own disposition to such a title - or whether he may have accepted it for himself - it may be telling that he had an apparently distinct and unusual of way of addressing God in prayer: namely, his use of the Aramaic word abba. In most modern English translations this is translated as "father", but it was actually a much more intimate form of address than that. A more apt translation might be "daddy" and such a degree of familiarity that apparently left its mark in the memories of subsequent generations (and is retained even today in the Lord's Prayer). So while Jesus may have considered himself (and his disciples?) to be [a] "son of God" in some significant way, the evidence that he considered himself the "only-begotten" Son of God is almost completely absent from the synoptic gospels.
Of the other Christological titles attributed to Jesus in the NT, their historicity suffers from the fact that they are only sparsely attributed in the NT and then largely absent from other early texts. It is sometimes claimed that Paul may have conceived of a high-Christology - based on possible allusions in his writings to Jesus' pre-existence (Gal 4:4) or divinity (Phillip 2:16-11; Col 1:15-20) - but these claims probably stretch the available evidence too far. Paul was generally explicit and repetitive in his enunciation of other Christological themes, and if he genuinely conceived of such a high-Christology then its presence in only a couple of ambiguous passages is difficult to explain. That is, if Paul believed Jesus to be God incarnate, we might be entitled to ask why he didn't say so more emphatically, given how important such a claim would surely be to his wider theology.
As for the undeniably "high" Christology of the gospel of John, again we must note that the language and titles the author uses are highly idiosyncratic (that is, to be found almost nowhere else in early Christian literature) and were likely confined only to the community from which the author wrote. In part this may be a consequence of normal Christological development (i.e. gJohn, as the last gospel to be written, was always going to have a more advanced view of Jesus' nature than the other gospels) but John's Christology seems unique not just within the NT, but among all early Christian literature. Of course John's Christology would come to play a disproportionately important role in the formation of later Christian theology, but this does nothing to ameliorate the fact that his writings (the gospel and the three epistles) were representative only of the beliefs of the somewhat ostracised sect from which he was writing, and cannot be considered at all normative within early Christianity. Other Christologies - such as the Trinitarian formula - find literally no support in the NT at all.
So the evidence is complex, and difficult to summarise properly in one post, but if you want to ask me what my opinion is of how Jesus viewed himself and his ministry then I think we have to see that Jesus clearly viewed himself as having some (uniquely?) special relationship with God and that he saw himself as an important cog in some wider eschatological process, but beyond that it's difficult to say with certainty. He was a preacher, likely a disciple of John the Baptist, who continued to preach his mentor's message of repentance in the face of the coming eschaton, but who pursued no institutional aims or titles beyond his leadership over a small, but committed group of disciples. As per the conclusion reached by Raymond Brown, if he believed himself to be the Messiah then he likely had a rather different interpretation of that term as compared to the interpretations that came before him (in Judaism) or after him (in orthodox Christianity). If he believed himself to be anything else (e.g. the divine logos or God incarnate) he doesn't seem to have shared such beliefs with the world.