When you register cpt and taxonomies, remove the rewrite argument completely (use the default) and then go to your dashboard, and from Settings > Permalinks set permalink structure to (Custom Structure) and type
/my-custom-slug/%postname%
Screenshots:
The setting:
The result:
save changes, and everything should be just like you want.