Funding opportunities for non-european people going to Europe for a PhD in TCS
Never having worked or studied in Spain, I can not really help with local information. However, as I mentioned in the comments, the most obvious source for such funding in European universities (aside from internal university or departmental sources and local research councils) would be funding from the European Research Council. The ERC has many different kinds of grants, including training networks and personal grants, which can often be used to fund overseas students from. Additionally, the European Commission offers funding for postgraduates and postdocs via Marie Curie actions.

Further, there is the China Scholarship Council which also offers support for students wishing to study abroad. 

Then there are the industry scholarships: Google, IBM, Microsoft, etc.

If either of the students is female, then there are more options (see Google's Anita Borg scholarship, etc.).

Lastly, many European countries have bilateral agreements with China or Chinese institutions which may be another potential source of funding.