Do I need a decoupling cap for ICs that do not switch very fast?
You do need decoupling for all IC's that switch or carry analog BUT where the decoupling is located and how many there are is a matter of design. Noise happens and decoupling is essential to ensure that it does not 'happen too much" - but part of the designers role is to avoid blind and pointless use of excess decoupling. Placing a capacitor adjacent to each IC is traditional and safe enough but what matters is what is being achieved by the decoupling, not where the capacitors are located. 

The object is three fold


Reduce switching spikes and noise originating from an IC to such an extent that they do not interfere unacceptably with the operation of the system as a whole.
Reduce power supply noise to such an extent that it does not interfere unacceptably with the operation of the IC.
Providing a reservoir to handle current demand by the IC. This can largely be interpreted in terms of the other two requirements - but an IC that cares not about system noise and for which noise generated is unimportant may still misoperate if supply impedance is not low enough to handle very large demand peaks. Generally overall power supply impedance should be mostly adequate to this demand with the local cap "stiffening up" the supply somewhat 


The first two aims are complementary. At a board level, if you achieved either one wholly then you would not need to achieve the other. In practice they work together. Meeting the 3rd helps the other two. 

In your case, if space is constrained then moving the capacitor somewhere else or using one capacitor in the place of two or more others is entirely acceptable provided that the object that was originally aimed at** is still met. ie this places more effort on you as a system designer to properly identify and quantify your noise sources, to properly understand the  effect of noise on a given IC etc and to design a decoupling system that meets your needs. 

Note that a 0.1 uF capacitor is almost certainly not the ideal size per IC - not so these days and possibly never so. Certainly 0.1 uF is often a fine compromise, but if you are trying to fine tune the result you may want a larger of smaller capacitor or possibly even several in parallel or several of different sizes in different locations. Also, as capacitor technology has improved things like ESR and lead inductance are smaller, surface mount packages give better electro mechanical environments (eg lead length minimal from an eg 0402 cap) and you may be able to use smaller or larger caps than in previous eras. Some suggest that a 1 uF ceramic cap is now a better general decoupling element than a 0.1 uF "monolithic ceramic" cap used to be, and others argue that a 0.01 uF cap is better able to handle the faster switching edges and clock speeds of modern systems.

For demanding situations it actually helps to look at specific data sheets and look at impedance/frequency curves. Capacitors of the same capacitance made with slightly different technologies (even amongst eg ceramics cap family) and/or from different manufacturers can and do have different enough frequency/impedance curves to be worth being aware of.

In the case of your multiplexers you should be able to estimate "within reason" the noise spikes originated by your ICs and the effect of system noise on them. Then by orientation of ICs, location of capacitors at sensible and critical locations etc you will be able to reduce capacitor count to under 1 capacitor for every IC.

Cost You say " ... and cost constrained..." on this point you are far less "safe". An ADG719 costs about $US1 in 10000s, falling to maybe $US0.80 in 100,000s. Maybe somewhat less in Asia. A decoupling capacitor costs around 1 cent for a 0.01uF or 0.1 uF in production volumes.  Board space and mounting and inventory and ... costs more, but the IC also has additional costs. While every cent matters, a saving of perhaps 1% to 5% on a critical component should be a secondary issue. By all means eliminate the per IC capacitor if you can - but do not let cost be the deciding factor. 



In response to query


What kind of trouble would be caused by the fast switching? The mux switches between two channels of a video source, so it doesn't really matter if it bounces in between the two sources as long as it settles in about 10 ms


What's acceptable deep-ends largely on what you are happy with. 

If you have no other circuitry to react to noise spikes, or don't care about worst case outcomes, whatever they may be, then you may not care about generated spikes. 

If noise from elsewhere does not occur, or is sure to be at a level where the effect on the video or IC is unimportant to you then you may not care about incoming noise. Extreme worst case response to noise may be IC "SCR" latchup or even destruction - but this would be "less likely" with low as opposed to no decoupling. 

SCR latchup and death is a real world effect in some ICs. Less common in modern ones, by design.



Latchup

The following references cover latchup in a range of devices. Only some of the following is specifically relevant but all may be of general educational value wrt the possible effect of out of range input transients on ICs. 


Wikipedia  
Analog Devices CMOS analog switches


NB - this application note specifically lists "Analog Devices" brand analog multiplexer and switch products which are designed to eliminate parasitic SCR latchup problems. The ADG 719 is NOT on the list of latchup exempt devices. 
This article will briefly describe the causes, mechanism, and consequences of latchup and discuss available prevention methods. Although our aim is to give an understanding of latchup as it occurs in CMOS switches, similar principles apply to many other CMOS devices. Latchup may be defined as the creation of a low-impedance path between power supply rails as a result of triggering a parasitic device. In this condition, excessive current flow is possible, and a potentially destructive situation exists. After even a very short period of time in this condition, the device in which it occurs can be destroyed or weakened; and potential damage can occur to other components in the system. Latchup may be caused by a number of triggering factors, to be discussed below—including overvoltage spikes or transients, exceeding maximum ratings, and incorrect power sequencing.

Youtube CMOS latchup
Siliconfareast.com
Fairchild - CMOS 74HC - how we stopped it - 1987!
Microchip MOSFET drivers
Zarlink - CMOS