Looking for a tool that will randomly generate an image of a world map.
You don't go into to much detail of what you're looking for, my suggestion would be to use TerraGen ( http://www.planetside.co.uk/ ) which can generate 3d terrain. I would take these renders, view then from a top down angle, and piece together a rather detailed and unique world map myself.
Or are you looking for something that will create a random 2d map such as the World of Warcraft map?
Hero Extant: World Generator looks nice and it's open source.
Here's an article from the Procedural Content Generation Wiki for map generation
If you need further advice check out their forums.
Fractals are a popular method of generating random maps, and there are a few tools that are available. I've used Donjon with some success to generate base maps. It's not perfect though. John Olsson used to have another online map generator but it seems to be defunct now, the C code for it is still downloadable on the page.
It does generate many kind of worlds and maps.
Though very expensive, it blew me away the first time I saw it; CityEngine by Procedural