He should be introduced by the earlier prophets, like the prophet Muhammad --peace be upon him-- was introduced in Torah and Injeel at the time (maybe the current translations of the books do not contain these announcements, I don't know). We even know people in history of Islam who knew the prophet of Islam to be a prophet only based on what they were told by the Jew scholars, although they never become believers as well. The last proved prophet but has announced that no new prophet would be sent to guide people after him --that Jesus peace be upon him will return before the Resurrection doesn't contradict with this announcement obviously!-- so that any one who would claim to be sent as prophet would simply be a liar.
prophets should have miracles as another proof for their prophecy, to show they are the prophet announced by the previous prophets.
PS. About Miracles.
everywhere in Quran miracles are referred to as Signs (آیات), Clarifications (بینات) or Clarifying Signs (آیات البینات or آیات المبینات), but the signs that according to [27:93] people would know them when is show to them, thus if they don't believe then they would be Kaafir (denier). However, there are now people who can do many of such historical miracles, like in Sufism and Erfaan, even doing some of those deeds need not a person to be a strong believer, an atheist like those in India can do many odd jobs, but these are not miracles to prove their prophecy. Miracles of Moses was for he time of Moses, miracles of Jesus was miracle at the time, peace be upon both of them. Ad-Dajjal can kill and rise like Jesus rose his friend, but Ad-Dajjal is not even a believer. People will think he is God like Christians now think Jesus is God, but imams have thought us the benchmarks not to get lost. The miracle for the present time and upto the Day would only be Quran, no one till then can ever bring a book like Quran. That the previous miracles are no longer miracles is due to improvement of knowledge and knowledge completed with the last prophet, provided to us through Quran and the prophet's house-hold.