So how do you handle any sort of software development planning? Do you just tell the client "It'll be done eventually. I'll let you know when.", or would you accept that reply from your employees?
Estimating is hard, but it's an estimate. Problems usually arise when one gives an estimate of 'X days' and what the manager hears is 'It will take X days, and no longer.'
An estimate will increase in accuracy the more you know, so if you don't feel comfortable giving an estimate, ask the question: "What information do I need to know to give me comfort for an estimate of Y% accuracy" and ask more questions.
If each iteration is producing sufficient independent business value (e.g., not dependent on subsequent iterations), then you don't have to estimate the size of the "overall project" to determine if it is worth starting. That's actually a key part of the risk mitigation provided by agile/lean methods.