Blah, blah, blah, clichés are bad. That's the vibe I'm getting from the replies here.
For the record, clichés are NOT your worst enemy when writing...well, just about anything. Sure, there are things that make people think "Man, I really wish this person had done something more original," like the whole "get starter pokémon from Professor <insert tree here>" thing, especially if the main character just happens to be so late that the regular starters have all been taken. Heck, even the main character being late at the beginning can be something of a turn-off.
However, in my experience, most of the time it's not what you write, but rather how you write it. I myself have (rather unintentionally) written out a bunch of clichés for my various fantasy roleplay characters, and yet I'm respected by the whole of all the roleplaying groups I'm in for my overall talent, particularly my characters! In reality, there's really nothing wrong with most of the clichés one tends to find in journeyfics (except the one I've mentioned already; that one's just plain old and makes you look like an anime copier). It's just that they tend to be written very n00bishly and are found in pretty much every n00b journeyfic, and so they generally are associated with bad writing.
Besides, there are a couple of journeyfic clichés that can't really be done creatively, such as the method of acquisition of the main character's starter. Other than the whole "get pokémon from professor" thing, there simply aren't many ways to go about it. Befriending a wild pokémon? Maybe, but that has potential to be just as logic-defying as the other methods, if not more so. ("Leik omg I fund a injred suciune adn tok it too teh pkmn cetenr and it becmae my bestest freind") The other, probably most logical method (especially if you want to avoid professors at all costs or if your MC happens to not live in or near one of the starting towns where professors tend to hang out) would be a "family pet" sort of thing, if you're willing to accept the fact that a number of "pet" pokémon, like Growlithe, Vulpix, or Skitty, are species that every young journeyfic main character seems to have and that such a thing might turn away a few readers. =/
My advice for making a journeyfic: try to put an original twist on it, but don't attempt to create something that strays terribly far from the norm. Write what you know, especially if you're a newbie author. I've seen lots of journeyfics that have a number of typical journeyfic clichés that are really good; at the same time, I've also seen plenty of journeyfics that desperately try to be different but fail where it really counts.