Solution 1:

Starting from 18.0 release of setuptools (released on 2015-06-23) it is possible to specify Cython in setup_requires and pass *.pyx modules sources for regular setuptools.Extension:

from setuptools import setup, Extension


setup(
    # ...
    setup_requires=[
        # Setuptools 18.0 properly handles Cython extensions.
        'setuptools>=18.0',
        'cython',
    ],
    ext_modules=[
        Extension(
            'mylib',
            sources=['src/mylib.pyx'],
        ),
    ],
)

Solution 2:

You must wrap the from Cython.Build import cythonize in a try-except, and in the except, define cythonize as a dummy function. This way the script can be loaded without failing with an ImportError.

Then later when the setup_requires argument is handled, Cython will be installed and the setup script will be re-executed. Since at that point Cython is installed, you'll be able to successfully import cythonize

try:
    from Cython.Build import cythonize
except ImportError:
     def cythonize(*args, **kwargs):
         from Cython.Build import cythonize
         return cythonize(*args, **kwargs)

EDIT

As noted in comments, after setuptools deals with missing dependencies, it won't re-load Cython. I hadn't thought of it before, but you could also try a late-binding approach to stubbing out cythonize