A creature can take Touchstone at level 1
The Sandstorm feat Touchstone (53) has as part of its prerequisite the following: "Knowledge (local) 8 ranks for the area in which the touchstone lies, or possession of a touchstone key (a portable object native to the touchstone’s area and worth at least 250 gp)." All a player must really do to have a PC start with the feat Touchstone is convince the DM that before play began his PC had an appropriate touchstone key, took the Touchstone feat, then somehow lost that touchstone key.
Alternatively, with the DM's permission, a freshly minted PC that begins with excessive starting gp—like a level 1 aristocrat (DMG 108) that starts play with 6d8 × 10 gp or a lucky human PC that possesses the background feat Noble Birth (Dungeon #92/Polyhedron #152 30) that sees such a PC start with double the normal starting gp—could afford to purchase outright a touchstone key before play begins. Such a purchase should enable the PC to enter play possessing the feat Touchstone unless the DM rules that's impossible, saying that starting gp is windfall recently received or something similar.
However, "[t]o forge a link between yourself and the touchstone, you must spend a day in meditation, spending 10 XP and 250 gp in material components," continues the prerequisites of the feat Touchstone. "Alternatively, the key object for the touchstone can be destroyed as part of the ritual, in place of the material components." Thus a freshly minted PC starting with 0 XP can't start a campaign linked to a touchstone site. She'll have to adventure a little first, but, seriously, that's, like, her and 2 friends versus a lone toad.
Note that it's actual possession of the touchstone key that grants the creature access to this feat if the creature doesn't have the 8 ranks in Knowledge (local), so, technically, destroying the touchstone key to link to the site without possessing a second touchstone key to the same site causes the feat's benefit to be lost, severing the creature's connection to the site. This reader therefore recommends instead the 250 gp in material components instead unless touchstone keys are readily available at the local Publix.
"Besides their prerequisites, what's the difference between Planar Touchstone and Touchstone?"
So far as I can tell, the only other difference between the two feats is not in the feats themselves but in the sites presented in their texts. When a creature that possesses either the feat Planar Touchstone (Magic of Incarnum 207 having the last word on that feat) or the feat Touchstone visits for the first time a planar touchstone site like those from the Planar Handbook, the creature automatically gains the site's higher-order ability, yet when a creature visits for the first time a nonplanar touchstone site like those in Sandstorm, the creature must meet the site's recharge conditions first before the creature can gain the site's higher-order ability.