So, I'm easing myself into the world of DJing, but as many DIYers, what I can't afford, I attempt to build :). Currently, I plan on using an Arduino and miscellaneous inputs (potentiometers, buttons, rotary encoders) to MIDI-out to my USB MIDI cable. Seem feasible?
Definitely feasible.
My first Arduino project was a MIDI footswitch controller for turning on/off softsynth guitar effects. You just combine the standard Arduino button tutorial with the Midi tutorial (as Richard linked to) and you're off to a flying start. 
Hardest part was soldering the friggin' DIN connector. 
I'm assuming I just make use of 4 16-input multiplexers (not daisy-chained) for a total 64 inputs? Would there be a chance of "missed" presses?
Would there be a chance of "missed" presses?
Why are you using an analogue multiplexer if all you want to detect are presses? You should only use analogue multiplexing if you want to measure an analogue sensor. As taking a digital reading is much quicker than an analogue one there is more chance of missing an event with analogue. However, you actually not miss an event but you might get un acceptable latency with too many sensors to scan.
This project uses analogue inputs n a MIDI context :-
http://www.thebox.myzen.co.uk/Hardware/MIDI_Footsteps.html
I'm not just using presses. That was just a worry. I'd be using a few sliders (pots).
What kind of controller exactly are you trying to build?
And what is going to be at the other end of the midi cable?
So you don't miss anything because the sliders will stay at the value until you read them. At worst there will be a small lag (latency) between you operating them and seeing the effects. This is likely to be in the order of less than a tenth of a second depending on how you do the software.
What kind of controller exactly are you trying to build?
Read the original post. It's a DJ controller. Basically, it's a coordinated panel of buttons, switches, and sliders that send a MIDI signal to activate an effect, start a loop, change a deck's volume, etc.
And what is going to be at the other end of the midi cable?
The controller goes to my computer's MIDI in. At that point, under Virtual DJ, or rather any DJing software, you map out your buttons to functions in the software.
What's the best way to get a large number of digital inputs, since buttons (obviously) aren't in need of an analog reading? Should I use a multiplexer for the sliders and shift register for the buttons?
In the ShiftIn tutorial, there was a guide on daisy-chaining 2 CD4021s. To use more, would I just jumper 9 and 10 to the next CD4021 and 11 to 6?
That shield uses 74hc595 output shift registers to expand the number of outputs available. You could theoretically swap them out for input registers, assuming the pinouts are equivalent.
I think I found my solution:
Centipede Shield
Also, this is the way you define controls under VDJ:
Controller Definition (MIDI)
Under VDJ, there are effect names, loop names, etc, which can be routed out to displays. Anyone know of places that sell 1x10 char displays, preferably in colors (like blue or red)?