I wouldn't have wanted to make all those fiddly shapes without one, but it wouldn't be impossible. I generally recommend to people with a budget that they invest in a tablet rather than software—Inkscape and the Gimp are both free as well as powerful.

You can draw with a mouse, but I find it to be more difficult to be accurate, and far more fatiguing. You could also try some other methods to create detail without a hardware investment. If you have access to a scanner, you could draw with pencil and scan it in. For something like this, I'd use a layered tracing paper approach, so you could create each shape on its own sheet, scan, run a trace in your software, then color it and layer them together. There are also several ways to add detail to a path using filters. You'd make a simple shape, then run the filter to get jaggier lines.

It also wouldn't be too difficult to create a map like this one in one of the programs dedicated to mapping, such as Campaign Cartographer or Fractal Mapper. You'd also have the advantage with those of getting automatic scale calculations, pre-built symbols, and easily-applied fractalization filters. The disadvantage, of course, is that they're not free, but they're significantly less expensive than Illustrator or CorelDRAW, and slightly less expensive than a Wacom tablet.