The idea of building a massive Federal network of 6 line highways was around long before it came to fruition in 1956 and obviously, Nazi Germany built its Autobahn system at the same time, so what if construction had begun on a 40,000 mile network of highways in 1936 instead?
I see two major problems with the Roosevelt administration beginning construction of the Interstates. The first is simple: the idea was underdeveloped at the time. In reality, 1936 is about when the federal government seriously started to study the idea of building a superhighway network (versus the federal highway network, with lower quality roads), mostly because of the expansion of state-funded roads in the previous decade, the growth of automobile and truck traffic, and the resulting pressure on the highway network and evident need for a more integrated system. And then it took about twenty years of study and planning to come up with a really good system to put in place. So to start construction in 1936 you really need to have started seriously looking at the idea probably in the mid to late 1910s, which in turn probably means that there needs to have been a lot of traffic then, which is not really that plausible without advancing the automobile at least somewhat.
The second problem, which is linked to the first, is that at the time state authorities were quite active in building new highways, and in fact built some quite good highways that would later
become Interstates; the Pennsylvania Turnpike, for instance, was opened in 1940 and presently carries segments of I-76, I-70, I-276, and I-95. And the federal government was supporting this through various methods, like providing funding or supporting inter-state cooperation in the numbered highway system. So especially in the 1920s when you really need to be laying the foundations for such a project, there wasn't any apparent need to be planning on building superhighways directly as a federal responsibility, and just a more limited oversight role would probably seem reasonable, particularly to the Republican administrations of the time.
Probably your best bet to achieve this without mucking around too much would be for the Harding Administration to take an interest in the Pershing Map of 1922 and start pushing and studying that proposal, with that momentum carrying onwards into the Coolidge and of course the Hoover administration, with work likely actually beginning under Hoover in parallel with other infrastructure and works projects like the Hoover Dam. The problem is the typical American disregard for defense needs at the time, so the military value of the highways would probably be discounted, along with the small-government attitudes of Harding, Coolidge, and Hoover that would tend to discourage them from starting such a large, expensive project (I mean, it is still one of the most expensive public works projects of all time). It's very difficult for me to see a reason why these Presidents and their administrations would show any great interest in this kind of project, even to the level of just performing studies like the aforementioned "Toll Roads and Free Roads" or "Interregional Highways".