It will be difficult to provide you a comprehensive answer, there are just so many potential variables. Let me see if I can address a couple of things.
Kanban and estimating: Don't. Kanban's value is in setting up a continuous flow of work. Prioritize the backlog, break work into the smallest valuable pieces and have the team pull the work from the top of the backlog. Limit work in progress to focus on getting things done. Once you get into a flow you will start to see cycle time trends which can be used to figure out what can get done by a given date.
Sprints and data over time: If each project is truly unique I can see some issues. I'm betting, though, that project to project have similarities (same code base, same general application, etc). If so, you can use past sprint data of a different project to plan for sprints for a new project.
Fixed Scope/ Fixed Deadline: This is your key issue. As long as the business thinks this is possible, then you'll never progress out of fire fighting project work. The only thing that happens in an FS/FD project is quality suffers. Then, over time, you will end up spending more and more time on fixing and less on building.
Unfortunately, we will never get away from Fixed Deadline. It's just not in human nature to not latch on to a date as "ship". So you have to focus on getting the development org to predictability (cycle time, stable velocities) with similar sized stories. By doing this, the team can reliably say "We can do X work by the release date" and have the data to back it up.
Good luck.