Guess what? You boss needs to build an X in 9 months. You have to figure out how many people are needed to build X, even though no requirements document is even remotely near completion.
How do you estimate number of humans needed, what they can do, and some very basic time lines with nothing to go on?
Are you sitting down? The answer: you're going to guess.
Whenever someone asks for estimates, if they're a good person, typically they tell you that you will not be held to those estimates, and its for planning purposes only, etc. This is not the case here. Your boss is looking to find out how to resource your team to accomplish a specific goal within a specific time frame with no more (and probably less) knowledge than you have about who and how to do it.
Some people, at this point, squirm. "I can't give an accurate assessment until I know what I'm building." This is logical, truthful, and beside the point. Unless this is an amazingly rare event at your company, this has been how they've done business for a long time (and how a lot of companies, even companies that use Agile or eXtreme Programming or other fast-track methodologies) have to do things. All projects are frameworks. A company or division or group builds a framework based on the initial idea (a scope document if you're very lucky) and the number of humans it would take to make that idea work, based on conversations between the program manager, product manager, stakeholders, and human manager (whoever is in charge of the developers, testers, dry-wall installers, nurses, cantina dancers, etc.).
These initial estimates fill out the appropriate teams and the amount of work those teams are estimated to be able to accomplish fill in the initial milestones.
To make this work, therefore, you have to do a few things:
1) Use your ability to investigate and talk to people to find out as much as possible about the project; if you have some team members, bring them in on their expectations, questions, and estimates.
2) Use your own experience on such projects to project pitfalls and problems as well as solutions and workarounds and how much time that all takes.
3) Build a basic idea of the stages of the project. Step A: Build X, Step B: Build Y, Step C, in parallel with step B: Build Z, Step D: Profit. Figure out how long each step should take to hit the specified timeline. Run this past a member of your team, if you can, just to check your work.
4) Assume the best case scenario. One person on each step exceeding milestones and possibly singing "Whistle While You work." Or maybe additional people for each step to finish early. NEVER SHOW THE BEST CASE SCENARIO TO ANYONE. Period. Pretend it doesn't exist if people ask.
5) Assume a worst case scenario. Everything that could go wrong does go wrong - you get Q when you finish with Step A, for example. You have to replace 1-2 key information experts during the course of the project. Perhaps a natural disaster occurs.
6) Create an "average" scenario. In this scenario, you assume things go wrong, but go wrong as normally they've gone wrong on any previous project. No scenarios involve the building on fire, but could account for a cooling fan breaking on a server.
7) Do some MATH. I hate math, so I hate to advise this, but you need to do it. On average, I tend to triple the time of the best case scenario to get the time for the worst case, then average that against the time and resources for the "average" scenario. The important part is you have about 20% more resources and time picked out for the "average" scenario when you go back to talk to your boss.
8) Do a little more math; I have rarely walked into my boss's office and said, "I need 4 of these guys and 3 of these guys and 2 of these guys" and gotten exactly what I asked for. Now, your mileage may vary boss to boss (or his boss to the boss above him), but I like to ask for about 35% more than I've estimated, so I can be happy with getting 20% more than I think it will take.
9) Prepare to put your estimates in a spreadsheet and make it look official. I recommend diagrams and charts, as well.
10) Talk to your boss about your estimate; use plenty of qualifiers like "This is off the top of my head based on the fact the project hasn't been fully scoped."
11) Before agreeing to any manpower/time decisions, get agreement on the most important part of the Iron Triangle - if meeting the deadline is most important, get agreement to cut scope as well as increase resources (increasing resources alone has rarely ever gotten a project out on deadline because of the costs of bringing resources up to speed); if the importance is the features, then get permission to extend the deadline (as well as add more people). Once you get a verbal agreement, send an email to your boss with the verbal agreement in it, and then SAVE THAT EMAIL.
12) Give your boss your estimates. Send a copy through email, as well, and store with the agreement in #11.
As the project ramps up, a weekly status report will be your savior (and not just another annoying task). No matter the project management method in use, your boss (and maybe his or her boss) will want to know what happened during the week. Further, these reports are a list of what you knew, when, and what you did about those things; so no furious boss in six weeks wondering why Step B isn't complete when he's be4en getting a weekly report about how you're blocked by a decision from him before Step B can be completed.
Weekly status should include:
1) A Red, Yellow, or Green designation on the project progress, where red is "things are going badly and we're going to be late/miss features/blow up the moon", where yellow is "things are not going the way we need and we're in danger of being in the red zone," and green is "everything is hunky dory."
2) Every member of your team an a one sentence (short) of what they did that week. Include people who went on vacations, holiday time, etc.
3) Any major wins
4) Any set backs + solutions for resolving them; include any upcoming vacations, for example, that might reduce the resources of the team for a period of time.
5) Any blocking issues (even issues that block you that your boss cannot help with must go in the report so you have a written log of why you didn't do something at a specific time...for example, you could not because you were waiting on something from facilities).
The report should be half a page or less, and should be done in bullet points with explanations about the report within the report. While you are sending it to your boss, and your boss knows all about your project (you may even talk to you daily about it) your boss may forward your report. It therefore needs to do it's job--tell your boss where your project is and its status--but it may also serve double duty as information to executives, who appreciate their data in small, consumable chunks that is visibly color-coded.
With a team in place, requirements in better shape, UPDATE YOUR ESTIMATES. As soon as you know of new information, pass it along. Talk to your boss. Uphold your agreement about the important sides of the Iron Triangle.
Then wade in there and do the project.
There is no perfect solution to being asked for an answer when you don't have all the facts. The above is a guideline of techniques to help you through it. At the end of the day, trust your team, and your gut, and work from there. Both team and gut instincts will either be right, or get better as the project progresses.