first, get rid of the split between 'testers' and 'developers'. Everyone tests
second, in TDD, the developers code the tests before they code the feature/story
What you have described is not TDD [it may be Scrum though; Scrum is a project-management methodology independent of the development methodology; Scrum is not relevant to your problem]
Scenarios where automated testing is impossible are exceedingly rare. Scenarios where automated testing is difficult, expensive, or inconvenient are much more common - but it is precisely these scenarios where automated testing is needed the most.
From the vague description, I assume the software is drawing something on the screen. If what is being drawn is determined by data, formulas, or functional steps, then at least write automated tests that test to the level of the data/formulas/functional steps. If the screen output is deterministic (the same steps result in the same drawing output every time) then test manually once, take a screenshot, and let future tests compare the output to the verified screenshot. If the screen output is nondeterministic and not governed by data, formulas, or functional steps, then you're in that rare area where automated testing may be impossible. But I doubt it.
I'm guessing that the only reason testing has not been automated so far is that the developers don't care about it. In TDD, the developers do the testing, so they feel the pain of the boring repetition of testing the same 62-step process a hundred times until all the bugs are gone. Nothing will get an automated testing solution developed faster than making the developers do the testing.
I don't think you'll really get anywhere without reworking the way things are done right now.
One example is that during development we only focus on new features
and ignore existing bugs and even introduce new bugs.
I am fairly certain that this is a grave mistake. Try to explain that bug fixing becomes more difficult and more expensive the longer it is postponed. I don't think there is any excuse for postponing bug fixes for so long.
All agile methods I know emphasize that the software should be technically ready to ship at the end of each cycle/iteration (or even continuously). That means any bug that you wouldn't want to ship must be fixed before any new features is started.
Try to work with people, and explain your concerns.
Finally, if you cannot get any kind of agreement on such basics, it may be best to move on.
Edit
Based on your amended question: I agree that bug fixing should be handled just like new features. I'd normally have single tasks for "small" bugs (up to a few hours) and stories with subtasks for "big" bugs (multiple days, possible to split into tasks). If your colleagues do not agree, point out that the advantages of agile methods apply to bug fixing just like to new features.
As to wheter to use an agile tracking tool or a bug database: Ideally, the two are integrated. If they are not, then yes, you'll have to track work in both. It's annoying, but I've done it myself, and didn't find it a big problem. You track bugs as usual, and just copy&paste the bug id into the title of a task/story when you schedule a bug to be worked on. The task is just a link to the bugtracker (eays if both are web-based), and all discussion is in the bug db. If you link consistenly, you could probably even run reports across both systems.
Finally, it you believe you cannot change the way development is organized, you'll have to work within these constraints. Things like introducing some agile methods into the bug fixing phase will probably help.
Still, I am convinced that splitting development into a "feature phase" and a "bugfixing phase" is a grave, possibly fatal mistake. It may not be so serious for your company (every situation is different), but if it is, and if your organization is unable to change this, then your organization may be so dysfunctional that you'd be better off elsewhere. But that is your call to make... good luck!
Edit 2
Finally, if company policies dictate "features first, bug fixing later", maybe you can sidestep them, e.g. by redefining bug fixes as new features (the difference is often a matter of opinion anyway). To some extent, you can try to introduce new ideas "from below" that way. You know, "if you can't beat them, join them".
Best Answer
Your system engineers are right; in practically any SLDC including Agile, your users should not be given a version of the software for their testing until QA green-lights it.
However, Agile allows for the development of software in sprints, and when each sprint is complete and green-lit by QA, it should be pushed to UAT for the users to bang on and give feedback. This is as compared to Waterfall or similar SLDCs where the deliverables are spread further apart and the user doesn't get software to test until initial development is very near complete.
So, I say in this situation both parties are right, but you're more right. You need separate UAT and QA environments so that QA can test what they're testing and UAT can test what QA has green-lighted for UAT release. These will almost certainly be different release versions of the software; QA should be one or two iterations ahead of UAT, and Dev should probably stay at least one sprint ahead of QA.