It's hard to get a list of all the regions in Second Life. SignpostMarv has been building tools to find all the regions for a while, but his list is down at the moment back up - see the (large, XML) sitemap. Second Life Surveyor also seems to have a complete list.

For each grid coordinate there's an API to fetch the region name:
https://cap.secondlife.com/cap/0/b713fe80-283b-4585-af4d-a3b7d9a32492?var=x&grid_x={X}&grid_y={Y}

So in theory you could go through all possible grid coordinates (y = 1 to 1280, x = 1 to ?) and see if there's a region there. A bit time-consuming and millions of hits to the API server, so not ideal.

It's possible to find region names and UUIDs through Linden Labs' Google Search Appliance, but of the 21,000 total only 2000 are available this way (1000 sorted by descending date, 1000 by ascending date):
http://search.secondlife.com/client_search.php?q=http://world.secondlife.com/region/*&site=Places&sort=date:D:R:d1&start=0
http://search.secondlife.com/client_search.php?q=http://world.secondlife.com/region/*&site=Places&sort=date:A:R:d1&start=0
(the UUID is in the link: http://world.secondlife.com/region/{UUID})

After finding regions using the search appliance, there's an API to fetch the grid coordinates for each named region:
https://cap.secondlife.com/cap/0/d661249b-2b5a-4436-966a-3d3b8d7a574f?var=foo&sim_name={REGION-NAME}

The image tile for particular coordinates is available:
http://secondlife.com/apps/mapapi/grid/map_image/{X}-{Y}-{ZOOM}-0.jpg
(note that the y-coordinate of the image tile is 1279 - grid y coordinate, and small islands only show up at the highest zoom level, 1)

To teleport to the center of any region (as regions are 256x256), use a link like this:
secondlife:///app/teleport/{REGION-NAME}/128/128/0/