How do I display content to users who are not logged in instead of 404 on Private custom posts?

Are you doing this inside The Loop? I’d try something like this myself:

if ($post->post_status == "private" && !is_user_logged_in()) {
    echo "You must be logged in to view this page.";
} else if( $post->post_status == "private" && is_user_logged_in() ) {
    // Page code goes here
}