Automation would definitely help. It will help in reducing the time for regression testing. But if you have Sprints running in tight schedules, you won't have much time for automating the test scripts. In such a case:
a) Define your testing acceptance criteria at the start of the Sprint.
b) Run a round of system testing on the application / new feature when released for QA.
c) Focus on testing the main functionality and detect critical bugs as early as possible.
d) Your best bet to start regression would be at the start of the second round of testing, i.e. when the defect fixes start rolling in. This will help to ensure that existing functionality is not impacted by the scope change / new feature.
e) If your regression test suite is large, you might need to prioritize the tests to be run. You definitely don't need to run the full gamut of tests. Test only those areas which are directly impacted by the scope change.
In the Long run, Automation is definitely the best bet. If not Supported by the client, take some time off and try automating the app. Even if it is not supported by the client (budget issues etc.), explain to your PM about the value add for automation.