It may seem crazy, but I am very familiar with the rental industry and know that the following pieces of equipment should be available most anywhere. For vertical digging, especially if you're not a super operator, skip the excavator and rent a towable hydrovac (vermeer vx30-500) It's basically a pressure washer and dirt vacuum in one. You can get 1-2 cyds in the smaller units that most national rental companies have. To cut the 36" x 36" definitely a diamond saw. If it's more than 6" thick, you can't use a 14" handheld demo saw. The saw can cut 3/4" less than the radius of the saw blade. So 14" is good for 6.25", the most common walk behind units are 18" and 20-24" cross over into self-propelled models. Make sure that whichever route you go, get a bug spray/pressurized sprayer. There has been some new laws that are making counties/municipalities really crack down on silica and airborne dust. Use the water sprayer (or a water hose) to keep the cut wet (better finished product) and keep the dust down.
Normally the whole silica thing isn't a big deal, but if you're luck is anything like mine, you would be cutting for the one time a year that you'd need to be, and you get hammered by the environmental police for making dust and airborne harmful contaminants. Hydrovac should be between $600 a day-$1300 a week, not more. If that breaks the budget, diamond saw and post hole diggers.
Hope that helps!
DP