This should do the trick. The category tables' structure in ExpressionEngine is really simple and using SQL is more powerful than any of EE's category tags:
You'll need to enable the Query module if you haven't.
sql="Select g.group_name, c.cat_name, t.title, t.url_title
From exp_category_groups g
join exp_categories c
on g.group_id = c.group_id
join exp_category_posts cp
on c.cat_id = cp.cat_id
join exp_channel_titles t
on cp.entry_id = t.entry_id
where g.group_id = 4
order by g.group_name, c.cat_name, t.title asc"}
I didn't fill in the
if statements. You'll need some conditional logic to figure out when in the loop to show a group or category heading and start a new list, because those are on every result returned. That might need to be PHP, so you can keep track of the previous value and compare them.
GWCode Categories also fills in many of the gaps in EE's category tags.
exp:query tag is a great technique to master, as it offers 'middle ground' between EE's tags and doing custom PHP/app dev. You're right (in your comment) that you'll lose out on some built-in parameters, but you may be able to include some in your SQL. Check out GWCode Categories too, though. It might offer solution and its docs include plenty of examples.