You’ve got yourself a real catch-22 there indeed. If you go for the analog input sleep option, using pull-ups will probably leak some current through the ADC input capacitor as well. Did you try setting all pins to digital input with internal pull-up OR digital output written low before going to sleep?
I use Freescale excuse me NXP Kinetis MK20 controllers, which are based on the same Cortex cores as the STM32, together with this excellent library for very satisfying results. The library saves the pin state, then puts all pins to output low and goes to sleep. When it wakes again, pin state is restored and the program continues as if nothing happened. The controller uses around 15µA during sleep.