Maybe not so hard as you might think. On my openSUSE desktop, uninstalling python3 would remove only calibre and virt-manager. Most of my server/container/vm installs don't have any python version. Perl isn't much harder to get rid of depending on the use case, for example some development stuff uses it.
I'm also not sure distros generally care about LSB. Debian dropped it years ago and did any distro even bother to implement it correctly?