I've begin some preliminary work on random battlefield generation!
[...]
Right now, the plan is to create an algorithm that intelligently cobbles together dungeons out of 5 x 5 prefabricated chunks. (Below is a picture of one such chunk.) I haven't 100% decided on all of the details yet, but I imagine that hallways will mostly be 3 x 5 in size, some with destructible objects to form choke points. I'll post more about it tomorrow when I make more progress. 
The tough part of random battlefield generation is making diverse maps while avoiding isolated areas. They're great to increase the replayability of the game by adding diversity to multiplayer games and campaigns.
How random will the generation be? Is it just random, or do you have something more complicated? I understand the idea of the 5*5 chunks but I fear some obstacles will still be there, namely the problem of choosing a "good" neighbouring tile.
I was thinking about it and I have a somewhat simple but not perfect approach. You can think of tiles or chunks (like the 5*5 tiles you presented).
Lets start by defining an array P(i,j,k) of n*n*4 with probabilities (or something similar). The 1st number, i, would be the index of the current tile, the 2nd number, j, the index of the neighbouring tile and the 3rd number, k, would be the position of neighbouring tile: North, East, South or West.
Starting with any position on the battlefield (random choice), we would choose the 1st tile type i randomly.
The next tile type j would be chosen in the following manner:
- Choose a random position k, restricted to the ones that are not occupied;
- Choose a neighbour j in that position, with probability P(i,j,k)/(sum over all jj of P(i,jj,k)).
Now choose one tile that has "free" neighbours and choose the next tile. Repeat until the board is filled.
A more difficult approach would be a creation of paths such that all walk-able spaces are connected (if you don't want isolated sections of the battlefield). After that, the algorithm would need to choose the appropriate tiles for the walls of the path, having in consideration the neighbours' tile types.