I have long been annoyed by our broadband provider (and wifi router supplier) disabling WPS on our router. But today I found out that it is actually possible setup the printer without a WPS capable router!
Run the hp-setup tool and select Wireless/802.11 while the USB cable is connected from the printer to your computer, and you should be able to set up the WIFI connection for the printer (you might need enable WIFI on the printer first).