Hail.

[Mirage]

While leveling, you'll generally target mobs that are a bit below your own level. Because of that, level correction formulas will keep your evasion rate up, so you won't need a lot of tools to help you. Skilling up your ninjutsu skill will take a while though, but this is definitely best to do when you're level 99, because then you have access to nin tool expertise, to save tools, and money won't be as much of an issue anymore. While you level, I'd say you should only bother with Utsusemi, and then only if you bump into decent challenges, or several of them at the same time. Or if you're low on health and don't have a way to heal yourself.

As for the fame requirements, you need a certain level of fame to quest certain ninja scrolls, which are used to teach you the spells which you later need to spend tools to cast. These scrolls can also be bought from other players, but because the game only lets you quest them once per character, they cost a lot. It will take a while, but you only need to do it once, and it is used for a lot of other quests too later in the game.

For an overview, try http://wiki.ffxiclopedia.org/wiki/Reputation for the reputation levels in various areas, and http://wiki.ffxiclopedia.org/wiki/Quick_Reputation for tips on methods to grind up reputation. Keep in mind that repeatable quests often just gives a little bit reputation per repetition, while non-repeatable quests often give a bit more, but you can't do them as mindlessly as repeatable ones. You might actually risk having to explore the world!