Regarding NoSQL solutions: CouchDB is an option, but I can also suggest MongoDB, which "ships" with a nice documentation and quite mature APIs (http://api.mongodb.org/) - including Haskell, Erlang, C++, Python, Java, .... . Maybe worth giving a try :)
Regarding MySQL I agree with Paolo that PostgreSQL seems more powerful than MySQL. For details refer to a rather old comparison: http://www.bostongis.com/PrinterFriendly.aspx?content_name=sqlserver2008_postgis_mysql_compare
I would like to add (it just came up to my mind) that another possible option (since there is the necessity to deal with relationships) might be to resort to a graph database: for example HyperGraphDB (http://www.hypergraphdb.org/index)
neo4j is a good option (due to property graphs supported), but the suggestion of Paolo - hypergraphdb - goes even one step further, as hypergraphs are supported (nb! an edge may connect any number of vertices). For details just refer to Wikipedia or Google - there are tons of papers around.
Also keep in mind that PostgreSQL can be extended with external functions written in several programming languages like C (and C-like ones), python and so on (take a look here http://www.postgresql.org/docs/9.0/static/xfunc.html). This means that you can use whatever library you can find out there: for example the boost graph library (http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/index.html) which is a prototyped library for graph handling, however, last time that I checked, it does not provide direct support for hypergraphs. Still, if you need hypergraphs you can find a suitable library and write your own extension functions for PostgreSQL.
I support the Neo4j option. There is also some good and easy-to-learn drivers for Python, Scala, Ruby, Javascript, etc. Native support is for Java, but using Cypher, the query language, any of the REST bindings works good for that amount of data.
In the end, neo4j turn out to be too slow either. MySQL works fine, but splitting data over multiple tables. Data is redundant, but access time very fast!
I think Neo4j and Titan support those amounts of nodes and relationahips and have decent Python clients. OrientDB possibly too, but I don't know about the Python support.