If I build a hello world application using a modern version of Qt4, what would be the minimum version of Windows my program could work on?
Would it work on Windows 2000, or even on older releases, like NT or Win95?
hard to say since QT is an open source project and you also need to consider the compiler as possible variant, but there are solutions even for Windows 98 Compiling Qt for Windows 98 and Windows 2000/NT is still supported on really recent releases like the 4.7 and 5.0 is supporting them as well.
I suppose that the real issue is Windows 95, but you really need Win95 ?
This days there are free OS that are production ready and user-proof.
Sometimes you will find references to Windows 95 in the QT wiki like at the bottom of this page, but at least for the 4.x branch it's unclear if it's supported or not, the branch 4.x is capable of supporting up to Windows ME, at least according to the platform notes from QT/Trolltech.
Probably with something like the version 4.3/4.4 you can get a QT environment under Windows 95.
EDIT
answering to your edit I will say that supporting Windows 2000/NT it's not an issue, supporting older OS will require a downgrade for your QT version and Windows 95 it's a lottery.