You've got the right idea. That's what you'll need to do to get it to work. Changing the palette colors will affect any tiles that also use that palette. You'll need to make a new palette and load it into CGRAM(hopefully not all palettes are being actively used) and then change the tilemap for the tiles you're editing to reference that new palette.

VSNES is a good starting point. You can view the tilemap and CGRAM from a savestate right there. What you'll need to do though is make some trace logs and find the code that loads that tilemap to VRAM. You'll need to find where the source data comes from for that tilemap and edit that data to reference another palette.

Loading your new palette data will of course require a small assembly hack to load your new palette data. It might be tricky figuring out where to insert that routine depending on how your game code is structured. I'd probably recommend starting with the tilemap load and working backwards from there trying to see if any routines around there are unique only when the tiles in question are loaded.

You don't want to stick it in a common routine because it will load that palette data whenever that routine is run potentially screwing other tiles up later.

In Geiger's tracer, just push the '*' key when you want to start/stop code.
There's several options, such as filtering out repetitions of the same code ("Squelch"), and to split trace logs (which can grow to be several megabytes per second) across multiple files (good if your computer can't handle opening 100 MB text files)
(too bad he doesn't post old versions. The most recent version (Mark 9 release 8)'s trace logs have kinda messy formatting. Version 8 had the register data lined up nicely, making it easier to quickly glance for changes. But 9.8 has much better debugging options.

Jope, I solved the palette problem 

But on an easier way - I just edited a color which was almost not used and gave the affected tiles another, similar color.

Thanks a lot for your help. Also I was able to get some trace logs

But, may I ask for another advice?
I want to make a time related item stable (it is only 10 minutes available)  but don't know how to get the correct address. It can be stabilized using a 7exxxx Par code but this afffects only ram and I need the rom address to create a patch. The log file is so huge and I don't know for which value I shall look in the cpu log. I know that I have to use somehow breakpoints (but also there I miss an address) or, as another possibility that I find game genie codes (but this isn't supported by zsnes cheat search...).