Ok, I came up with a solution. The key was not to use the flow backing bean @PostConstruct but rather use the flow initializer, where I can grab request parameters.
So I'm using some additional input in the form that will start my flow:
<h:form id="myForm" prependId="false">
    <h:commandLink value="Enter myFlow" action="my-flow"/>
    <h:inputHidden id="parameter" name="parameter" value="8"/>
</h:form>
In my flow definition I've defined an initializer for the flow, calling some method in the flow backing bean
@Produces @FlowDefinition
public Flow defineFlow(@FlowBuilderParameter FlowBuilder flowBuilder) {
String flowId = "my-flow";
    flowBuilder.id("", flowId);
    flowBuilder.initializer("#{myFlowBean.startFlow()}");
    ...
}
I've then grabbed the parameter inside the backing bean.
@Named
@FlowScoped("my-flow")
public class MyFlowBean implements Serializable {
    public void startFlow() {
        String parameter = FacesContext.getCurrentInstance().getExternalContext().getRequestParameterMap().get("parameter");
        //now do sthg with the parameter, such as fetching data from an injected service
        ....
    }
}
Of course it's also possible to do that at the flow definition level 
flowBuilder.initializer("#{trainingFlowBean.startFlow(param['parameter'])}"); 
and just have a parameter in the startFlow method 
public void startFlow(String parameter) {
    ...
}