I think the trouble you'll have is finding all the missions and doing them in order. As a foreign character, you won't get any of the quests, not even primaries, offered in the areas before Kryta. Those primary quests lead you to the missions. Some Tyrian missions do leave you in the next mission outpost upon completion; others leave you in a non-mission outpost and give you a primary quest to follow to the next mission.
Yes, it's spoilers, but it may help you keep the storyline in order (and not miss any missions) if you follow the
Prophecies storyline guide on wiki. If you don't want any spoilers, then I'd suggest starting a Tyrian character to progress through the story at least until arrival in LA to learn your way.
Yes, you can take a non-Tyrian back to the beginning of post-searing in Ascalon. (It seems to be a fairly common run offered from LA.) But you don't absolutely *need* a runner. If you've never been through Tryia, a runner will most likely get you back to the beginning a lot faster than you'd find it yourself. Bear in mind that most runs don't necessarily include stopping at *every* mission and non-mission outpost back that way.
In Tyria, all that's required for any character to enter a mission is that you get to the mission outpost. (Once there, you just hit Enter Mission as the party leader.) There are no "closed gates" between Ascalon and LA that would keep you from accessing missions or maps without the primary quests.
(There are a couple later on, but you'll have primary quests for those.)
Another surprise coming to someone from Cantha or Elona may be the bonus system in Tyria. Tyria has *almost* no timed missions, and no master's rewards. Each mission has a primary objective, listed in your mission log, and a bonus objective
(that displays once you trigger it, similar to the bonus objectives in NF missions.) There's no Standard/Expert/Master reward. Primary objectives completed get one sword through the mission outpost town; bonus objectives get a second sword. (I forget which way each sword goes.) You don't usually have to finish a mission to get credit for completing the bonus objective. Protector of Tyria requires all the missions and bonuses completed but doesn't require that you do them on the same run.
Foreign characters, and post-searing Tyrian characters can't access the pre-searing everyone speaks of. That very first starting area is a completely separate map with a story set 2 years before the rest of Tyria. Once a new Tyrian character leaves, they can't go back. Luckily for the purposes of titles, the area has no missions or explorable map that count towards the protector or explorer title tracks.
I wish you luck, and I'm glad to hear people are still interested in Tyria.
And I totally agree with others that if you really want to see the first chapter in all it's glory, you gotta start with a brand new Tyrian character.
Cheers,
Luny