I have successfully being deploying database changes like this for years, and in most cases it is quite simple.

For the most part we use stored procedures and we apply a version to the stored procedure names eg. GetAll____v1, GetAll____v1, Add____v1, Add____v2 etc.

This means when I change a database structure I can add stored procedures to work with the next generation of the code, and if required, make a modification to the existing version to allow the current version of code to continue working.

...and of course, all new table columns require either a default or to allow NULL. In most cases I simply allow NULL and have the developers handle this in their code - it makes deploying to the live database servers much simpler !