Thank you for sharing the details on what you have already tried - that helps a lot.
I assume prebuilding failing with the same error of missing pybind11/pybind11.h, correct?
So, next, let’s do a very simple thing? Check that you have pybind11/pybind11.h in your python environment that you use to build deepspeed.
I see that it comes bundled with torch, so e.g. I have it under my conda env:
/mnt/nvme1/anaconda3/envs/py38-pt18/lib/python3.8/site-packages/torch/include/pybind11/pybind11.h

So in your case there should be one under /usr/lib/python3/dist-packages/torch/include since this is one of  -Is include statements in your error log. So for some reason you probably lack:
/usr/lib/python3/dist-packages/torch/include/pybind11/pybind11.h

and if it is so, then your package is borked.  I have no idea how you came about this package, it appears like some non-conda/non-pip distribution package - but is it possible that it has torch and torch-dev packages? In which case you’re missing the dev side of things, which would have all the required headers. At least that’s how all .deb packages are made.
So if you installed this package as:
apt install torch

you now need:
apt install torch-dev

At this point you probably want to tell us what OS/dist you’re on and how you installed torch.