I'd go with Optimizely. If you want to also send the data to a server for analytics external to Optimizely, you can use their API.

Optimizely is good service, but I am looking for something cheap that I can install on my server(s) or that can work with Google Analytics. I am looking for feasible solution that can work for millions of user.

Million users are not even part of Optimizely's standard package (I assumed it is going to be expensive).

I wish I can use Optimizely client side APIs with free Google Analytics :)