I get that this is a rhetorical question, stated in such a manner to imply I have insufficient context of the real requirements of this project and cannot gauge the size and complexity of it. But, I've got a full cup of coffee, so I will take a shot to see if I can address this impossible situation.

  - hire an entire department's worth of people

The worst approach I can imagine is to start this project by hiring new, dedicated people. This project only succeeds by incorporating it into the very fabric of an agency's operation. Remember, new work must go on even after this API is in place. Hiring a dedicated group that somehow has to reverse-out everything the agency does going forward for purposes of external API access is a recipe for failure. Separate teams will already be at odds with each other; better to leverage the existing teams, as their the ones in best position to understand the context of how external access to their operations should function.

  - wait for them to devise an API for your agency

I'm not sure if this refers to a lack of understanding the requirements, or to a lack of competency on the part of the team itself, but the presumed outcome is late delivery. If it's complex requirements, that simply suggests a basic, iterative project where scope is managed tightly and the duration is rather short (allows the team to learn as the project moves along.) If the suggestion is competency on the part of the team, hiring/contracting a few competent individuals to align with team leaders on the project has worked well for past projects. In either case, proper management of the project approach can address issues of timeline.

  - code it

This goes to team capability, but also to an understanding about integration. Again, solvable problem based on the team capacity. If this suggests a unique code stack that's not already available elsewhere, I'd need to understand the justification. Project management 101.

  - provision server space and servers

This implies the technical operations of our agency are fully-loaded, or can't address this in a reasonable timeframe, or purchasing requires some inordinate amount of lead time, or some other unknown reason. If the suggestion is that dependencies exist that threaten the timeline, those dependencies should be mitigated. Again, project management 101.

  - deploy

This is a physical step of pushing bits live, so automation tends to make this a quick step. In my project, we thought about deployment actions when we determined how to devise our API. At this point, deployment is an operational aspect -- not a how-do-we-do-this function. This project doesn't proceed without understanding this step.

Disclaimer: I've actually done this type of project work for significant operations of size and complexity. I've also worked with a few federal agencies, so I have some familiarity with the lay of the land.

It's really not that daunting of a project. I would respectfully suggest that you re-consider your own presumptions, as there are a lot of ways to address this type of work.