Odd. That's not right, 72dB attenuation (i.e., 20*log(2^12)) at Fs/2 only applies if you need < 1 LSB error (due to aliasing of higher frequencies) exactly at the highest frequency you can sample. But that's not the point where it becomes a problem. If your signal is baseband, then the 0-1kHz range has the first in-band alias product at 19kHz, which gives quite a bit of help to your filter design. The insufficiently filtered 10-19kHz range will alias to 10-1kHz, which can be filtered digitally.
So yes, as long as you include the aliasing effect -- you are quite correct, filtering can be traded off both before and after the converter.
There should be a theorem about bandwidths -- you only want as much as you need, at each stage of the signal path, period. What's the first thing you should do after conversion? More filtering, of course! Depending on platform, that could be quite rich, or fairly modest. Even the most basic platform can do a simple sliding average (boxcar filter, has a sinc(f) response) at that sample rate; an AVR or PIC at typical speeds (10s MHz) should be able to do even more (e.g., several stages of biquad IIR filters, in a suitable filter characteristic -- from among the usual suspects, Butterworth / Bessel / Chebyschev / etc.). Even if it's just a simple 1-2-2-1, or 8 or 16 length sliding average, it's good practice.
And what you're doing depends on how much noise the output should have. If only 0-1kHz signals are counted as output, then perhaps you won't even bother with digital filtering! The analog filter needs only to go from <pass band tolerance> dB at 1kHz, down to -72dB (ish) at 19kHz (for which a 5th order filter should do well enough, I think?).
If the output needs to be clean -- essentially, whatever's reading that digitized 1kHz signal actually has more bandwidth than 1kHz -- and it needs to be cleaned up first, then you need either a very aggressive analog filter (it rolls off as sharply as necessary, just above 1kHz), or whatever product of digital and analog gives the same result (the dB's add, so you can trade attenuation in one filter for the other, making note of course of where aliasing causes it to fold back on itself).
An example of "high bandwidth" and therefore sensitive signal processing might be, a zero-crossing detector for phase or frequency detection (the tight filter is effectively required because the zero-crossing decision is only made based on the samples nearest to zero: the filter incorporates proceeding samples as well, putting more data into that decision and making it more robust).
Or a mixer process (like an audio effects pedal that does a ring modulator effect, or what have you), where aliasing again shows up, and you need to control the sidebands carefully.
And if you don't truly need 1 LSB freedom from "noise", you can make the filter that much looser in capability. (Example: a more sophisticated zero-crossing detector that does a line or curve fit to the samples near zero; or best of all, a Hilbert or Fourier transform, which computes its answers from the totality of all samples in the array and is its own filter!)
If your signal source isn't even that dirty, you might not need much if any filtering -- and indeed, aliasing might even be beneficial, too. If the source frequency and sample rate are harmonically locked, then no beat frequencies will be produced, and you can get something akin to equivalent time sampling. In that case, digital averaging (especially if it's done over an array of samples, binned based on a trigger time) effectively limits the bandwidth as usual, but it tightens the bandwidth to the same amount around every multiple of the sample rate (including 0, i.e., the original baseband fundamental signal).
And if your signal is aperiodic in the first place (e.g., control loops), aliasing isn't a concern, and all those extra filters are only slowing down your loop -- in this case, you still want filtering, but only to reduce interference (especially e.g. switching ripple), with a minimal impact on response time.
Tim