It's not hard to give rough estimates for a project's time frame. I work in software and something like, "We expect feature A to be complete by date X" is not unreasonable and is pretty standard. If you reach date X and feature A is not complete, then give a reasonable explanation as to why feature A is not finished, something like, "we ran into difficulties implementing feature A because of reasons B, C, and D."

This "we don't do deadlines" thing is a little ridiculous. Set reasonable time frames and, if they aren't met, give explanations as to why they couldn't be met.