I don't think the folks that say this usually mean "never done before" in the way that you are saying.
"never done before" in my experience usually translates to "this combination of things doesn't have precedence internally [to the team or company], so I have to figure out how to glue all of these parts I don't understand together".
"never done before" in my experience usually translates to "this combination of things doesn't have precedence internally [to the team or company], so I have to figure out how to glue all of these parts I don't understand together".