In 1.9, the Passengers tag will hold a list of the entities riding a host (in which the riding stack is reversed from 1.8's Riding compound). You would first label the zombie as though they did not have a squid riding their head, and change their label if there actually was.

  1. Removing label from zombies by default first:

    /scoreboard players tag @e[type=Zombie,tag=hasSquid] remove hasSquid
    
  2. Adding label to zombies if squid is riding:

    /scoreboard players tag @e[type=Zombie,tag=!hasSquid] add hasSquid {Passengers:[{id:"Squid"}]}
    
  3. Example of a result, saying the names of zombie who did not have a squid riding them:

    /say @e[type=Zombie,tag=!hasSquid]
    

The opposite (giving the squid the label as well) is not feasible to do perfectly accurately in 1.9. You would have to rely on setting the score of the nearest squid to the zombie.

However, since only squids that do not have the label are being targeted, there will at least always be the same number of squids with the label as there are zombies. It does not necessarily mean that the squids with the label are those that are riding a zombie.

  1. Removing label from squids by default.

    /scoreboard players tag @e[type=Squid,tag=hasSquid] remove hasSquid
    
  2. Adding label to the nearest squids without labels.

    /execute @e[type=Zombie,tag=hasSquid] ~ ~ ~ /scoreboard players tag @e[type=Squid,tag=!hasSquid,c=1] add hasSquid