Printer connected to Airport Express.. Works without AirPrint?

Wrong. You can print from Mac, but not from iPhone.
The thing is, AirPort Express/Extreme only wirelessly extends the USB cable. You need a matching printer driver on your Mac to make it work.
iPhone has no printer driver(s). And AirPrint is a driverless printing protocol.
There are AirPrint activators available, however. You need to keep it running on a computer for as long as you need your AirPrint printer visible on iOS devices. That way, your computer pretends to be an AirPrint printer and will send it's output to a printer that's been configured to print on that computer.

 

You need printNshare installed and webprint too. With these two apps you should be able to print, but to be frank? I'd buy an AirPrint capable device.

Theses require no real setting up beyond entry of your wifi details, then off you go.

 

I just recently installed a HP LaserJet Pro MFP M127fn. Despite being visually ugly as hell, it lets our iPhones to AirPrint without any problem! And didn't break the wallet either.