Hall sensor confusion with unipolar and bipolar as well as magnetic induction sensitivity
with bipolar sensors I think I'd need two magnets, one near the other
  oriented with opposing poles towards the sensor, one would make it go
  high and the opposing pole from the second magnet passing by would
  make the signal go low,


No. A single magnet has both north and south poles, so with correct orientation it can do both. Two magnets would only be required if you wanted the output to go high and low at widely separated positions on the wheel. 


  Let's assume, for the sake of the argument, a typical fridge magnet at
  5mT as per Wikipedia. With the unipolar versions of the sensors with
  the TLE4905 (page 8 of the data sheet linked above) the strength of
  the magnet would not be enough to trigger the sensor which has a
  Bop=7.5mT. The TLE4906 is a bit more sensitive at Bop=6.5mT, but still
  not enough.
  
  Is this right? Now I either need a stronger magnet or a more sensitive
  unipolar sensor, right?


Yes. Best solution may be to use a Neodymium magnet, which is much stronger than a fridge magnet.