Mr, Rick,
Since your POD is TR getting the GOP nomination in 1912 I believe that it might have the following consequences:
1. In OTL TR's VP running mate was Senator Hiram Johnson of California. This made sense both politically (Johnson was a leading Progressive Republican and he was willing to make the jump to the new party) and geographically, balancing TR's home state of NY. I do not think Johnson would have been a good ticket balancer in your TL.
2. Assuming that TR has won a hard fought battle with Taft for the nomination or that Taft withdrew from consideration because of some sort of health problem, I think that TR would need to choose a running mate either from the conservative wing of the party or at least not actively toxic to that wing. That rules out Johnson.
3. Charles Evans Hughes is also out because as a fellow New Yorker, under the 12th Amendment, a TR/Hughes ticket would forfeit tht electoral votes of NY. A reliably conservative midwesterner would seem to be a lolgical choice but I do not have an individual in mind.
4. I agree that Lodge wouold be a good choice for Secretary of State. However, if he wished to stay in the Senate, perhaps TR could convince his friend Elihu Root to return to the job. If TR is the GOP nominee, perhpas the bad blood between TR and Root that developed in OTL because of Root's efforts for Taft at the convention can be butterflied away. For Attorney General perhaps the former U.S. Attorney for the Southern District of NY who was serving as Taft's Secretary of War, Henry Stimson. For Secretary of War, TR's old friend Leonard Wood. For Secretary of the Treasury, TR's friend and campagin finance chairman, George Perkins. For the Secretary of the Interior, TR's friend Gifford Pinchot (if the Taft wing can swallow someone that Taft had fired for insubordination as Chief of the Forestry Service).
5. As stated above, Brandeis would be a good, coaltion building choice for Secretary of Labor if he could be convinced to serve in a GOP administration. Brandeis was really the first of the "superlawyers"; a lawyer who was known throughout the country and who had a national practice.
6. I have my doubts about FDR for Secretary of the Navy. In 1913 FDR was a young, partisan Democrat who had only served a few years in the NY State Senate. Aside from issues of nepotism that such an appointment would raise, TR did not have an overwhelmingly high opinion of his distant relative who had married his favorite niece. Like many in the Oyster Bay Roosevelt family (and in politics in general) FDR was considered something of a lightweight. Charming, but not very smart.
Your obedient servant