Getting a dump of arXiv metadata
My main confusion was not realizing that The Open Archives Initiative Protocol for Metadata Harvesting is a separate protocol, not a subset of arXiv API.

In this case, the relevant queries are ListIdentifiers (10k items per query) and ListRecords (1k items per query). To get just identifiers we need to write:

http://export.arxiv.org/oai2?verb=ListIdentifiers&amp;set=math&amp;metadataPrefix=oai_dc


It results in 10k identifiers in the following form:

&lt;OAI-PMH xmlns="http://www.openarchives.org/OAI/2.0/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd"&gt;
  &lt;responseDate&gt;2015-02-16T19:28:22Z&lt;/responseDate&gt;
  &lt;request verb="ListIdentifiers" metadataPrefix="oai_dc" set="math"&gt;http://export.arxiv.org/oai2&lt;/request&gt;
  &lt;ListIdentifiers&gt;
    &lt;header&gt;
      &lt;identifier&gt;oai:arXiv.org:0704.0002&lt;/identifier&gt;
      &lt;datestamp&gt;2008-12-13&lt;/datestamp&gt;
      &lt;setSpec&gt;math&lt;/setSpec&gt;
    &lt;/header&gt;
    ...
    &lt;header&gt;
      &lt;identifier&gt;oai:arXiv.org:0712.1769&lt;/identifier&gt;
      &lt;datestamp&gt;2011-06-23&lt;/datestamp&gt;
      &lt;setSpec&gt;math&lt;/setSpec&gt;
    &lt;/header&gt;
    &lt;resumptionToken cursor="0" completeListSize="249546"&gt;760571|10001&lt;/resumptionToken&gt;
  &lt;/ListIdentifiers&gt;
&lt;/OAI-PMH&gt;


As there are more results, to get next batch we need to specify resumptionToken, in this case:

http://export.arxiv.org/oai2?
   verb=ListIdentifiers&amp;resumptionToken=760571|10001


and so on.

Other useful parameters are from and until, e.g. as in

http://export.arxiv.org/oai2?verb=ListIdentifiers&amp;set=math&amp;metadataPrefix=oai_dc&amp;from=2015-01-14&amp;until=2015-01-14


To directly get categories (bear in mind that set=math specifies mathematics, but there are no smaller subsets), one can write:

http://export.arxiv.org/oai2?verb=ListRecords&amp;set=math&amp;from=2015-01-01&amp;until=2015-01-31&amp;metadataPrefix=arXiv


It's important to set metadataPrefix=arXiv, so that subdisciplines will be listed:

&lt;categories&gt;
  math-ph cond-mat.other math.MP nlin.CD physics.class-ph
&lt;/categories&gt;


EDIT: 

I used delay as Nate Eldredge suggested, in my case - 25s. Yet, while trying to get all math (250k items so in 250 queries) it gave error at 70. I did continue it (with even higher delay) but sometime around 110 the query was not longer available.

So, the way to go is in getting smaller chunks - e.g. by month (or for mathematics - at most by year).