HostGator and A Small Orange are both cheap shared hosts I can recommend that ssh. The only shared host I have run into that didn't support SSH was $25 / month for 1 MySQL database and some paltry amount of storage space.
I'm sure there are a lot of cheap shared hosts that don't provide SSH, but there are hundreds that do, and the big players (who are the most reliable anyway) definitely do.