To eliminate the issues introduced by the native python on the Ubuntu 16.04 host, I've set up a new Ubuntu Host with all the native python packages removed.

But now when I try to build the make fails saying:

arm-linux-gnueabihf-gcc -shared -L/home/ubuntu/workspace/toolchain/gcc-linaro-4.9-2016.02-x86_64_arm-linux-gnueabihf/bin/../arm-linux-gnueabihf/libc/usr/lib  -Wl,--no-as-needed -o libpython3.so -Wl,-hlibpython3.so libpython3.5m.so
arm-linux-gnueabihf-gcc -L/home/ubuntu/workspace/toolchain/gcc-linaro-4.9-2016.02-x86_64_arm-linux-gnueabihf/bin/../arm-linux-gnueabihf/libc/usr/lib  -Xlinker -export-dynamic -o python Programs/python.o -L. -lpython3.5m -lpthread -ldl  -lpthread -lutil   -lm  
_PYTHON_PROJECT_BASE=/home/ubuntu/workspace/python/Python-3.5.2 _PYTHON_HOST_PLATFORM=linux-arm PYTHONPATH=./Lib:./Lib/plat-linux python -S -m sysconfig --generate-posix-vars ;\
if test $? -ne 0 ; then \
	echo "generate-posix-vars failed" ; \
	rm -f ./pybuilddir.txt ; \
	exit 1 ; \
fi
/bin/sh: 1: python: not found
generate-posix-vars failed
Makefile:598: recipe for target 'pybuilddir.txt' failed
make: *** [pybuilddir.txt] Error 1


Looking at the configure.log it complains of missing python as well:

python: not-found! cannot run $(srcdir)/Parser/asdl_c.py

Could you please comment if it is not possible to build python3 without first installing a native python on the build machine?

Maybe I have not set all the options to the ./configure correctly (e.g _PYTHON_HOST_PLATFORM).