This problem can also arrive when you have different Python versions installed and you use a pip that's not the system's one. In that case, the non-system pip won't find the right version of Python headers.
It happened to me when trying to pip install a package for a Python bundled with an application. As it was not system's python, apt install pythonXX-dev didn't work.
In this case, the solution is to find the right python header:
find / -iname 'Python.h'
In the output, you will see system python headers, and hopefully the one you are looking for, for example:
/usr/include/python3.7m/Python.h
/usr/include/python3.6m/Python.h
/home/ubuntu/workspace/blender-git/lib/linux_centos7_x86_64/python/include/python3.7m/Python.h
/home/ubuntu/miniconda3/pkgs/python-3.8.5-h7579374_1/include/python3.8/Python.h
/home/ubuntu/miniconda3/pkgs/python-3.7.0-h6e4f718_3/include/python3.7m/Python.h
/home/ubuntu/miniconda3/include/python3.8/Python.h
/home/ubuntu/miniconda3/envs/sim/include/python3.7m/Python.h
/home/ubuntu/src/blender-deps/Python-3.7.7/Include/Python.h
/opt/lib/python-3.7.7/include/python3.7m/Python.h
Then, you can set a compiler flag that will get used by gcc when called by pip.
Mine was /home/ubuntu/workspace/blender-git/lib/linux_centos7_x86_64/python/include/python3.7m/Python.h, so I did:
export CPPFLAGS=-I/home/ubuntu/src/blender-deps/Python-3.7.7/Include
pip install <package>