How do you minimize downtime for an ALTER?
There are two tools you can use to do this.

1) Percona's PT-ONLINE-SCHEMA-CHANGE which can be found here (Percona is a very big hitter in the MySQL world).

and there is also

2) Shlomi Noach's oak-online-alter-table which can be found here. Noach's c.v. is also impressive.

Public awards
Oracle Technologist of the Year: Developer award
Oracle ACE
MySQL Community Member of the Year, 2009 award.

Obviously partitioning could also help your speeds, but if you can't afford to partition now, these tools may be of assistance to you.