I don't really like the idea of tools, mostly because half of them would be weird to carry around. I mean a bike is bad enough, but carrying around a boat or surfboard along with a hot air balloon or jetpack would be bizarre.
Personally I think Pokémon should be able to learn "moves" that can only be used outside of battle. So in essence it's the same as what we have now, accept they can only be used in the field and not in battle. They're more like skills I guess. Birds can fly, so let them fly whenever they want once they learn how too. Pokémon with sharp claws can use them to cut etc etc. Those sorts of actions shouldn't be limited to "moves" because they're naturally occurring actions.
Tools wouldn't be THAT bad.
-Cut: Hatchet; small enough to carry around and cut bushes.
-Fly: Uh...I got nothing here that would reasonably work. Flying poke would be needed.
-Surf: Foldable Surfboard; easy enough!
-Strength: Same issue with Fly; would need a Pokemon for it.
-Flash: Flashlight; simple!
-Rock Smash: Pickaxe; bust them rocks up!
-Waterfall/Whirlpool: See Fly, Strength
-Dive: Snorkel and/or Dive Gear; simple enough to do.
-Defog: LOL
Really, you could just make Fly, Strength, and whatever else wouldn't work just field moves and have small tools for everything else.