I successfully use the approach of setting a cookie for the language instead of having it in the URI, then having all URI segments set in my pages database, for each language, then in my page model I load the correct language URI and text based on the language cookie.
Now the only remaining problem is routing, I set something like this in the end of my routes file, redirecting all remaining requests to the page controller method:
$route['(:any)'] = "main/pages";
$route['(:any)/(:any)'] = "main/pages";
This way I can have both page URI and submeny URIs with my localized version.