You could try part of the Lurujarri Dreaming trail that follows a song cycle north along the coast from Broome (Minyirr) to Coulomb Nature Reserve (Minarriny) via James Price Point. The Goolarbarloo people are the custodians of this walk, so it's best to touch base with them first (they can help with water drops and transport).
http://www.goolarabooloo.org.au/minyirr.html As far as other walks on the Dampier Peninsula, it's mostly all Aboriginal Land, so you would need to contact the individual communities. You could (possibly) follow the coast from the Middle Lagoon Campground
http://www.middlelagoon.com.au to the Whale Song campground (08-9192 4000) at Munget on Pender Bay. Freshwater is your biggest problem on the DP.
Cathedral Gorge and Echidna Chasm at Purnululu will only take an hour each. The drive between the two takes longer than either walk. If i had the time (and water) I'd do Picaninny.
Mornington Wilderness Park
http://www.awc.org.au, 95km off the Gibb has plenty of walking opportunities along some of the larger gorges, i'm sure if you talked to them you could organise an overnighter. Most of the pastoral leases along the GRR have some sort of walking action, I'd check out Mt Hart, Mt Elizabeth, CHarnley River and Home Valley. If you want to go hard-core off track consider Drysdale River National Park. See the DEC site for all the relevant contact numbers
http://www.dec.wa.gov.au and you can find the GRR station contacts here
http://www.gibbriverroad.net