How was the virus Smith able to get back into the Matrix without the Trainman's help?

Smith must have had the Trainman's help.

First, some background:

When Agent Smith was destroyed by Neo at the end of The Matrix, he was flagged for deletion.

You destroyed me, Mister Anderson. Afterward, I knew the rules, I understood what I was supposed to do but I didn't. I couldn't. I was compelled to stay, compelled to disobey. And now here I stand because of you, Mister Anderson, because of you I'm no longer an agent of the system, because of you I've changed - I'm unplugged - a new man, so to speak, like you, apparently free.

What were those rules he was talking about? The Oracle had just previously explained:

The Oracle: ...usually a program chooses exile when it faces deletion.

Neo: And why would a program be deleted?

The Oracle: Maybe it breaks down. Maybe a better program is created to replace it - happens all the time, and when it does, a program can either choose to hide here, or return to The Source.

Since Smith chose to "disobey", he was evidently an exile hiding in the Matrix.

As you know, the Trainman controls Mobil Avenue, which is used by exiles to enter the Matrix. It is also important to note, however, that the Trainman works for the Merovingian -- so, effectively, the Merovingian controls who can enter the Matrix through Mobil Avenue.

In Neo's case, the Merovingian ordered the Trainman to keep Neo in Mobil Avenue because the Merovingian hates the Oracle and therefore opposes Neo (because, as The One, Neo is part of the system devised by the Oracle which rendered the Merovingian obsolete). Preventing Neo from re-entering the Matrix prevents Neo and the Oracle from working together.

However, Smith and the Merovingian have common enemies in the Oracle and Neo (the enemy of my enemy is my friend). The Merovingian undoubtedly ordered the Trainman to help Smith so that Smith could work against Neo and the Oracle. This is probably also how Smith acquired access to the backdoors (see the second point).

It is possible that Smith somehow had access to the Matrix through some other route due to the fact that he was a former Agent. However, the fact that Smith explicitly says he is no longer an agent of the system suggests that this is not the case. Furthermore, the Agents don't seem to have a special route into the Matrix anyway, since Rama Kandra told Neo in Mobil Avenue that

I know that if you want to take something from our world into your world that does not belong there, you must go to the Frenchman.

Rama Kandra told Neo that this was the only way into the Matrix from the machine world, so it doesn't seem that the Agents have another route. Furthermore, as an exile, Smith "does not belong [in the Matrix]" so Smith would have had to go to the Frenchmen (the Merovingian) to re-enter the Matrix.

I don't think he ever left the matrix. When Neo joined with Smith and then split him, his pieces were scattered. But since Neo did join with him as smith indicates in part 2 as well as disclosing that because of Neo he was able to chose to not rejoin the source, it enabled smith to become a virus. I think the first reborn smith was his having taken over another matrix life form virally.

Therefore, since he never crossed over, he never had to cross back.

As agents of the system, Agents are evidently capable of entering the Matrix through the proverbial front door in those rare instances that they're killed; seen most clearly when Agent "Dodge This!" Brown is shot and killed by Trinity, but then simply returns a few minutes later. Smith seems to still have the ability to use this entrance, despite being recalled to The Source.

You destroyed me, Mr. Anderson. After that, I understood the rules, I knew what I was supposed to do, but I didn't. I couldn't. I was compelled to stay, compelled to disobey.

It's only exiles that need to find clever ways into and out of the Matrix and at the point that he resurrected, Smith evidently still had the credentials needed to use the normal Agent entrance. This is, of course a perfect case study as to why you should take door-entry badges away from recently fired staff.

In several answers, ex-Agent Smith is quoted and the key sentence is when he says to Neo, "I was compelled to stay". (Emphasis mine.) Not "I was compelled to return." This implies that he never left. He did not need to re-enter, because he didn't leave.

Dying, being deconstructed, or whatever happened to Smith did not eject him from the Matrix. Is there any evidence that when an Agent-inhabited blue pill is killed the Agent is ejected from the Matrix and requires re-entry? I think it boils down to: was Agent Smith's deconstruction at the hands of Neo so severe it would remove him from the Matrix and require re-entry, might it conversely have been so unexpected that the Matrix "flag him for deletion" code -- which I would mainly argue is only operative between Matrix versions -- didn't happen, or was it "business as usual" for an Agent to remain in the Matrix even after "death" or the death of a blue pill they were inhabiting.

I would argue that the "flagged for deletion" refers to programs from previous, different version of the Matrix who thus had to evade deletion in Machine World and sneak into the new Matrix via the train. That's certainly what we see in Merovingian's minions.