First time passenger flight by two pilots? In this video, the captain proclaims after take-off:

We were nervous about this, but takeoff went smoothly

It was his first passenger flight in the A350, but still... not exactly what I would want to hear as a passenger. This got me thinking, does it ever happen that two pilots take their first passenger flight on a given type together, or will it always be the case that if it's someones first time, the other pilot will have X amount of hours on that type?
It is never “the first time”. What he is really saying is that after many hours of flying the aircraft (or an approved simulator) this is the first time doing a revenue flight with passengers. Previous flights would have been training flights.
When a new aircraft type is first introduced to an airline, it can be expected that the entire crew is doing their first revenue flight after training.
What is not expected is that the pilots announce it to the passengers. I would not advise doing that because the passengers might not understand, and it would put doubts in their minds, as it did for you.