Which one to use? InnoDB Replication or MySQL Cluster?
MySQL Cluster possibly a good fit for you because of your key:value lookup traffic pattern. NDB is traditionally poor with joins or compex queries. I would say however that it is not the same as MySQL and has caveats that you need to understand before jumping into bed with it. It's shared nothing architecture means that you should operate it at scale with decent (and inclusive redundancy) network infrastructure. It is perhaps worth a proof of concept project to fit it out and test it. The guys at severalnines have configuration tools to get you up and running.  

Mongo isn't a bad fit either and as you state you cannot give up A_I, why not? What about values like (1902jdd,"/page/id") needs and auto inc? Mongo documents are schemaless and you add superfluous data to a document where you see fit and query in a key:value style too. Statistics moving forward would put you into the map reduce world which could be fun.

Keeping with traditional RDBMS and requiring performance you should look at memcached and the mysql memcached api for rapid key:value access to the data which would retain the relational aspect for aggregation queries (select [count|max|avg]... group by order by blah, blah...