Is it even possible to do this?

The goal is to group our visitors:

Group A sees Theme A
Group B sees Theme B

I am able to achieve this goal through cookies. But when caching is enabled (i.e. Site config > Performance > On), things are messed up. This is what happens:

1. Group A visits Page-1
   -- Page-1 is not cached yet.
   -- Cookies are properly checked.
   -- Page-1 is displayed using Theme A

2) Group B visits Page-2
-- Page-2 is not yet cached.
-- Cookies are properly checked.
-- Page-2 is displayed using Theme B
3) Group A visits Page-2
-- Page-2 is already cached.
-- Cookies are ignored
-- Page-2 is displayed using Theme B (when it should be displayed using Theme A)

So now what I am thinking is, instead of using cookies, I'll use separate cache for each group.

Is this even possible :S If not, any recommendations are welcome.

Inputs will be highly appreciated. Thanks!