it wasn't which, but rather env, I had those mixed up. The "issue" is described here: https://github.com/NixOS/nixpkgs/issues/6227

The problem there isn't that env isn't available (it is, we have coreutils in stdenv) but rather that /usr/bin/env (that specific path) does not exist in the sandbox.

What created more problems was that patchShebangs wouldn't work here because it appeared in a configure script that was created and run during the actual build process (I think the build process is horrible, but here it is in case you're inclined: https://github.com/BSI-Bund/TaSK/tree/master/tlstesttool the stuff in the 3rdparty directory gets downloaded, configured and linked against in the main program's build phase

Yikes, you don't want that.

so you have no opportunity to actually follow the solution in that issue

I didn't read the issue in full but, since everything is pre-downloaded, you can always fix these scripts.

For the auto-generated configure script for example, you'd have to patch the build step which generates the configure script to put in ${coreutils}/bin/env rather than /usr/bin/env. Simple as that.

3rd party repositories can be patched during their respective fetches. You have to inject them anyways since there's no way to download 3rd party repos during a build.

https://pastebin.com/0GwLk1wP if you want to see an example of my level of nix-fu. I have programming basics but the nix language can be confusing sometimes. I'd say I have a basic understanding of things but as said before the more intricate stuff still escapes me.

You have to differentiate between the Nix expression language and using Nixpkgs' frameworks to define packages here. These are two entirely different skillsets with only a slight dependence on the former by the latter.

If you take a look at your expression, it only required fairly basic Nix syntax: Simple function calls, declaring recursive attrsets, string interpolation and attribute access. Most packages are like this.
Figuring out which attributes need to be set how and what that means is an entirely different skillset. Defining patchPhase in that attrset is trivial syntax-wise but figuring out what needs to be substituted using which stdenv "library" function is something else entirely.

Looks pretty good btw. I'd look into whether the build could be coerced to link against Nixpkgs' versions of those libraries though instead of vendoring dependencies. Especially security-critical stuff like openssl. That'd probably also save you the trouble with the interpreter.
If you take a look at the build definition, there's this handy dandy USE_3RDPARTYBUILD option.

I'd wager if you did cmakeFlags = [ ... "-DUSE_3RDPARTYBUILD=OFF" ]; and buildInputs = [ asio zlib openssl ... ]; (from pkgs, not your fetched sources) it'd just work. (Might need pkg-config in nativeBuildInputs but I don't think it uses that and will instead discover those deps via cmake.)

If you can get rid of the vendoring, feel free to submit that to Nixpkgs ;)