You are correct in assuming cookies from another domain cannot be accessed. However, if it's on a subdomain, you should be able to access the cookies if they're set correctly.
If you absolutely must have them on completely separate domains, it's going to be a bit tricky. If you can't modify the existing PHP code, you can pretty much forget it.
One option would be using OpenID - that may be the simplest way to tackle this, as there are OpenID libraries available for PHP and Python. OpenID would allow you to have a single-sign on like authentiction, and since it's already used on various sites it is proven and works.
Another option is writing a custom single sign-on system.
The basic idea is that when a user arrives at your site, you direct them to a login site. This can be either in the PHP or Python end of things, or separate. Here, the user will sign in, and then the login generates a secret key - this can be a hash, random string, whatever as long as it's not predictable - and the user is redirected back to the main site with the key.
The main site then sees the user has a key, and sends a request to the login site behind the scenes to verify the user's key.
Now the user is logged in at one site. When the user visits the second site, it too redirects the user to the login site. Since the user had already logged in, the login site simply redirects the user back with a new secret key, and the second site verifies it from the login site and now the user is logged in without having to input their credentials another time.