I see a lot of sprite catalogs for games provided as single PNG image, like the one below. 
I'm interested if I have to manually create tiles from that, or if there's some program that can split it into various tile combinations for me? For example, given the tile combination below, I will have to create a flat grass surface, and 8 other combinations with various edges. Is there something that can automate this task?
Go to piskelapp.com , then choose 'Create new Piskel'. Click the menu on the right, and choose import your own image; select it, then put the number of size of each tile. After you are done editing, choose Export in separate images. Done!
If you're starting with a tileset with regular dimensions and layout (as in your example), and your goal is to create tile maps in Tiled, there is no need to use third-party tools. Tiled supports these natively and easily.
There are a few tutorials on using Tiled like this one, but it's very simple:
Add a new tileset from file, input its tile size and margin/spacing, if any (there is none in the example)
Start painting tiles. Your loaded tileset is in the sidebar.
There are also other handy features in Tiled; the trees you see in the tileset will be loaded as separate tiles, but you can use Tiled's Brush features to draw those trees in one go. There's also the Terrain Tool which helps you paint tile transitions, after you've defined the border tiles.
From there, it's best to treat the tile maps as a whole, via the frameworks that support TMX maps, rather than individual tiles. For example, you would load and render tile layers, or draw all your "wall" tiles in the same layer and perform a layer collision. There is usually no need to split a properly-authored tile set into individual tiles.
After a bit of struggling, I found this info:
1) Shoebox is an app that takes the map like I listed in the question and attempts to Extract Sprites, typically a whole blob of terrain
2) What I wanted to do next was split this image into 9 tiles, and be able to reassemble them in various combinations. Shoebox also seems to be able to do this (Extract Tiles). This creates a TMX files
3) It seems that the next step is to import the resulting .TMX map into a tile map editor, like Tiled: http://www.mapeditor.org/download.html . From the video, it seems that I would be able to rearrange tiles and create various combinations I need.
It appears that ShoeBox has a bug on mac where it appends the folder name before the png file name (Line 4) within the TMX file, so I had to remove it manually :
name="[REMOVE FOLDER]base_.... 
List of frameworks that support TMX maps: https://github.com/bjorn/tiled/wiki/Support-for-TMX-maps
