Your best bet is the one you already rejected: delete cascading. That ensures that the table that has the foreign key is always up to date with the primary table. However, if you cannot modify this table, your next best option would be to add a trigger. This is a different type of modification and it might be something that you could do. You would do an Instead Of trigger on the DELETE command. Before the delete, you would then delete all of the records from the foreign key table that correspond to the row being deleted.
If neither of these options are acceptable and you must do it in your query, you are going to need to do a SELECT on the rows you want to delete and then delete the items in the foreign key table that match. Once that is done, you can finish with the actual delete of the primary key table. It would look something like this (pseudo-code):
DELETE
FROM ForeignKeyTable
WHERE LinkingID IN (SELECT * FROM PrimaryKeyTable WHERE <criteria to="" find="" rows="" be="" deleted="">);
DELETE
FROM PrimaryKeyTable
WHERE <criteria to="" find="" rows="" be="" deleted=""></criteria></criteria>
Those two statements, working together, will delete all of the rows that reference the primary key table and then they will delete the rows in the primary key table as well.