To accurately estimate a project's time, scope, or resource requirements, you need to perform some analysis and estimation; this is true regardless of your chosen framework. One can generally accomplish this as a mini-project where an estimate for the "real" project is its primary deliverable.
Your other sub-questions will depend a great deal on your chosen project management framework. Waterfall is a model, while "agile" is a set of frameworks based on the Agile Manifesto. Some useful comparisons can be made, but specific practices can vary quite widely.
Below are some specific suggestions for how to accomplish your objectives, regardless of what framework you choose. The suggestions also attempt to highlight some of the differences between traditional and agile methodologies so that you can consider what might work best for your specific situation.
Timebox Your Delivery
How will I come up with the dates based on scope without having the team now?
You don't make these kind of estimates based on scope, because you have no way to estimate the level of effort or time required to meet that scope. Instead, if you want to be agile, you define a time box for each iteration and each milestone.
For example, if it's now March 1st, your client might define September 1st as their target delivery date for the project. Your team then has a time box of six months to deliver as much scope as possible within that predefined time box.
In addition, you will define iterations as additional time boxes within which you will commit to delivering a set of potentially-shippable features. For example, a six-month project will give you approximately 12 two-week iterations. In each iteration, the client will define what features they want to prioritize for that single iteration, and the team will commit to the scope of work they are confident that they can complete within that two-week time frame.
The time box and the goal for each iteration is fixed, but the scope of work that can be successfully delivered over the lifetime of the project is variable.
Kick Off a Project-Planning Project
How do I determine scientifically the number of resources needed to finish the release?
You can't. Oh, there are frameworks that pretend that they can, but unless your project is a manufacturing project with well-defined tolerances no initial guesstimate survives the real-world project process without changes in scope, time, or allocated resources.
In an agile project, the number of human resources is generally fixed (e.g. a fixed team size and/or a fixed number of teams), but the scope and the number of iterations will vary based on the needs of the project. This is generally what you need, but there are alternatives.
To provide a reasonable estimate of how much a project will cost or how many iterations it is likely to take, you must actually create a project spike to create those estimates. In other words, you might form a short project to go over the feature list (a.k.a. Project Backlog), define and estimate stories, and maybe even perform a short story spike or two. This sort of calibration project is actually quite common, and many larger clients are willing to invest in a "project-planning project" in order to gain more accurate estimates.
Waterfall and Agile Frameworks Have Different Value Models
How different are the estimates and estimation for an Agile project done vs. Waterfall?
Waterfall, even modified waterfall models, are basically designed around up-front planning and then trying to control for deviation from this initial plan. Because the Cone of Uncertainty is typically largest at the start of a project, up-front planning is generally not successful in controlling complex or complicated projects.
Agile methodologies, on the other hand, generally use just-in-time estimates at a granular level, thereby reducing the Cone of Uncertainty to more manageable levels. Frameworks like Scrum also provide for just-in-time analysis and design, which help to maximize the accuracy of short-term planning.
Another way to look at it is to say that both types of methodologies are bad at long-term estimation and planning, but agile frameworks acknowledge that and take a value-driven approach to delivering features frequently in a tight feedback loop in order to maximize value for the project stakeholders.
In short, if your project can deliver incremental value, then agile frameworks are a viable option. If your project truly can't deliver any value unless all predefined tasks are 100% complete, then frameworks that require up-front analysis and design and a less emergent production cycle may be necessary. Your mileage will certainly vary.