Custom post type permalink structure

function myrules(){
    add_rewrite_rule('^yourcptslughere/([^/]*)/([^/]*)/([^/]*)/?','index.php?p=$matches[1]&taxonomy=$matches[2]&name=$matches[3]','top');
}
add_action('init','myrules');

Replace the ‘yourcptslughere‘ with what you wanted, and then add that to functions.php then flush your rewrite rules, and the final example you posted should work. I doubt it will be what the_permalink() returns however so you will have to construct the urls yourself, however they should be viewable at those URLs e.g.:

example.com/randomcptslug/123/exampletaxonomy/testpost