An unelegant (and potentially labor-intensive) solution to the tile size issue could be to first generate a dense grid, then manually merge some of the tiles together to create larger tiles. Depending on the shape of the grid this could result in some oddly-shaped tiles, but aesthetic qualities aside that shouldn't cause any problems.

Another thing to consider is that if we're going to use the Mercator projection, then the size of mapped areas will vary greatly by latitude in any case.

I found this handy little program called DrawHexGrid that can be used to generate numbered hex grids of various configurations. Here's an example grid of 100x50 hexes:
Click image for larger version. 

Name:	hexgrid100x50.gif 
Views:	1523 
Size:	538.2 KB 
ID:	59942
Sadly it doesn't output vector files so resizing the grid to the dimensions of the map might be tricky.