For a given budget you know how much iterations can be done. The Product Owner should then prioritize the work to get the most value of the product backlog. This is how Agile works, fixed time and team size with variable scope (Agile is about scope management). And once the team velocity is known, you can forecast how much work (in points) can be done (# of sprints x velocity = size of the work that can be achieved).
Often, customer don t get it and wants "everything they think they need at a given time" (i.e. fixed scope). In this situation, you end up doing some kind of upfront analysis to brake down everything into small enough items to estimate them. Once this work has been done, you can forecast how much sprints you ll need by guessing on the velocity (# of sprints = total size / velocity). This is a very common situation for people with a waterfall background and will often lead to inaccurate end date (fixed scope and team size with variable time) because you can t really guess the velocity and the start of a project is the worst moment to do estimates.
In both cases, you ll need the velocity. The problem is that the velocity is actually 1) unknown before the team start to work and 2) will vary over time.
To solve 1), you could estimate guess the velocity as discussed in the second situation but this isn t very "Agile". Ideally, you should instead get the team start working to measure the actual velocity (which will be likely inaccurate during early iterations). An intermediary scenario is to give a first very rough estimate and to come back to the customer after a few iterations with a more precise one, once you ve gathered more knowledge about the project and reduce the uncertainty.
To solve 2), I track measured velocity over time and use the highest and lowest velocity and the average velocity of the last 3 sprints as work hypothesis. This allows me to do optimistic, pessimistic and realistic forecasts (respectively).