Drop the gravity
If your world has Mars-like gravity, it can have Mars-like mountains and canyons. Tharsis is a 7 km high plateau on Mars. Yarlung Tsangpo has an average depth of 2300 meters as it drops from a 2900 m plateau to a 600 m lowland. You could thus expect to get average canyon depths of 6000 m + with a highland as high and extensive as Tharsis (which is about the size of Russia). Consider that Tharsis is also a dead volcanic province on a dead planet. An active one might be even higher, and thus the canyon even deeper.
Make it dry
A large part of why the deepest canyons are underwater is that the Earth has a lot of oceans that tend to get low places wet. However, if there is less water, you can get some real deep places on land. A good example is the Zanclean period, when the Mediterranean was sealed off from the Atlantic at the Straits of Gibraltar and dried up almost completely. This would have exposed places up to 5000 m deep or more to the atmosphere.
For another example, what if the Red Sea was not open at the Bab al Mandeb? It is right in the middle of the desert, so it would be almost devoid of water; like a bigger version of the Dead Sea valley (already the deepest place on land). The Red Sea is over 3000 meters deep, and it is easy to imagine it being deeper, if the tectonic plates moved just so. Given how wide the Red Sea is, the grade wouldn't be steep enough to cause the walls to immediately collapse, even if it was 10000 meters deep. The island of Lombok is around 4 km high with a radius of 40 km and isn't collapsing; at that ratio you could get to 35 km deep where the Red Sea is 350 km wide.