You could use Stash by Mark Croxton to accomplish that without multiple channel entries loops. Here is the kind of code I would use with the dev branch of Stash.
{exp:stash:set_list name="mylistname" parse_tags="yes"}
{exp:channel:entries status="1|2|3" channel="listing" orderby="random" dynamic="no" limit="15"}
{stash:st_title}{title}{/stash:st_title}
{stash:st_status}{status}{/stash:st_status}
{/exp:channel:entries}
{/exp:stash:set_list}
{!-- get status 1 entries randomly ordered --}
{exp:stash:get_list name="mylistname" match="#^1$#" against="st_status"}
{st_title}
{/exp:stash:get_list}
{!-- get status 2 entries ordered by title asc --}
{exp:stash:get_list name="mylistname" match="#^2$#" against="st_status" orderby="st_title" sort="asc"}
{st_title}
{/exp:stash:get_list}
{!-- get status 3 entries ordered by title asc --}
{exp:stash:get_list name="mylistname" match="#^3$#" against="st_status" orderby="st_title" sort="asc"}
{st_title}
{/exp:stash:get_list}
That way you just use one channel entries loop to get all your entries in random order and build a stash list, then use multiple stash get_list to filter and order that list the way you want.
Hope it helps
EDIT see comment below.
You want a paginated list of all your 10000 entries, ordered by status (all entries from status one, then all from status 2, etc.) ... but you also want the entries from status 1 to be ordered randomly and the other two ordered by title.
(partial) solution 1: native tags
You can orderby status and then by title using native tags.
{exp:channel:entries status="1|2|3" channel="listing" orderby="status|title" sort="asc|asc" dynamic="no" limit="15"}
{title}
{/exp:channel:entries}
The remaining problem is ordering the status 1 entries randomly.
Solution 2: custom plugin
You could also look at extending the channel:entries module. Here is an article detailing the process. Obviously you will need to adapt it to your needs.