Hook user login never gets called?
Just add a (boolean) field to the user.


  For new Drupal 7 site you can use:
  
  Admin > Configuration > People > Account settings > Manage fields
  Another method is using Profile2 module, a successor of Content
  Profile Drupal 6 module If you have started with a minimal install
  profile you will need to enable the Field UI module to access Manage
  fields via the Account settings.


Then, in a custom module, invoke hook_user_load and there, check if it's set. If not redirect to a page where the user needs to accept the terms and this field get updated.

Or, have a look at EU cookie compliance, it does more or less what you want.