This is basically what happened at the Cretaceous-Tertiary extinction, and as a result the timeline of events for what would likely happen has been discussed to some detail in the scientific literature. Basically, nothing grew for years after the impact, most plant life on earth survived as seeds during this time. However, I cannot find a more specific estimate for how many years it took for new plant life to grow, I would assume at least two based on the link but I have heard estimates of up to a century before plants started growing again (though it would be cool in an apocalyptic way, I am a bit skeptical of this).
The general timeline of events is that herbivorous animals would have started dying out first, due to the loss of their food source. Carnivores would last longer, because they would be able to scavenge on carrion and feed on each other, but eventually they too would eventually dwindle and die out due to lack of food. Larger species would die out first. The animals that survived the K-T the best were those that were part of brown food webs (i.e., rivers) based on the breakdown of detritus as a primary food source rather than green plants, or could switch to feeding on aquatic prey. Others, like mammals, likely hibernated through the extinction (or fed on seeds).
The only difference is in your scenario the plants never came back. Eventually the brown food webs would fail because there was no longer organic matter being introduced into aquatic ecosystems. Small hibernators would wake up only to starve to death in the absence of food. Given that all plant life on Earth was nearly wiped out by the K-T extinction and yet we didn't all choke to death, it seems safe to assume that everything would die of starvation long before any lack of oxygen.
The question is are you counting non-plant photosynthesizers like cyanobacteria, algae, and phytoplankton as plants. Marine photosynthesizers produce 85% of the world's oxygen, and if you only wiped out all land plants life on land would be devastated but aquatic life would eventually continue with little change.