Gfrktyl

According to Wikipedia, history of rice, rice was first brought to South East Asia region across the caravan routes of the central Asian steppes. Now many of the subcontinental people of South East Asia, like people of Nepal, Bangladesh, Vietnam, Thailand, Malaysia, Sri Lanka, Philippines, many Indians, Pakistanis, have rice as a staple food. Though many other staple foods in different regions and ethnic groups exist, but mainly rice dominates the scene as staple.

My question is, what was the staple food of natives of South East Asia before rice became the staple?

From Pakistan to Japan is indeed a big region and "before rice" a long and varied time frame. But this question seems to imply that it is concerned with the early neolithic centers of agriculture in Asia and what the first main staple foods in these were, excluding all rice.

Short answer to that for the North-Eastern region in question, over the course of quite a few millennia: mainly millet, but also hemp, buckwheat, cucurbitaceous plants, and peas.

Jomon Japan as an example did all that (excluding hemp for while) from 5000 BCE before rice arrived only 2500 years ago via Chinese settlers. Compared to central Yangtze river society where rice first became the staple food 6000 years ago. Further South to the New Guinea system of agriculture starchy foods like sago, yam and taro went into cultivation and stomachs. Further West the influence of Mesopotamian innovation is felt and grasses like wheat make their mark after people relied on millet again and until people learned to know rice cultivation.

Despite the obsessive dominance of rice in the later Yangtze region of China, even in that area and North of millet species went into cultivation earlier, as early as >8000 years BCE. Conversely, rice itself did apparently not spread from China as the epicenter, but was domesticated independently in other regions of Asia as well. And the prehistory of rice cultivation in the early periods of China has some problems:

Research in South China emphasizes rice. Unfortunately, the literature is rife with unsubstantiated claims of early domestication. Zengpiyan cave (11,000 B.P.) has been assumed to have evidence of pig domestication and rice agriculture but recent research indicates that the occupants had no domesticated plants or animals. In particular, flotation samples document the collection of a range of wild plants, none of them small grain plants (Zhao 2003). The oldest directly-dated rice grains have been found in two areas: the Yangzi River drainage basin (6500 B.C.); and to the north in Henan at Jiahu (6000–7000 B.C.) (Crawford and Shen 1998).
_{Gary W. Crawford: "East Asian Plant Domestication", in: Miriam T. Stark: "Archaeology of Asia", Blackwell Studies In Global Archaeology 7, Blackwell: Malden, Oxford, 2006. (AoA)}

In any regions South of mainland China indigenous forms of agriculture had developed, often perennial vegeculture alone or in addition to annual crops. These regions often displayed some kind of resistance to the whole "neolithic package". That is taking ceramics quickly and only slowly adopting millet and even slower in adopting rice.

Interestingly, while agriculture spread South and rice went along with it, the more tropical climate necessitated also to transfer the principle but refrain from rice as well, until cultivars more suited were bred:

We have no evidence that any of them grew rice in the equatorial islands of eastern Indonesia or in Oceania, and it seems that this subtropical cereal faded from the economic repertoire as people moved south (Dewar 2003). In equatorial latitudes rice was replaced by tubers and fruits such as yams, taro, coconut, breadfruit, bananas, pandanus, canarium nuts, and many others, all originally domesticated in the tropical regions from Malaysia through to Melanesia (Lebot 1999). Neolithic populations domesticated or acquired these crops as they moved southwards and eastwards through the islands, and some might have been domesticated independently in and around the island of New Guinea, where evidence for swamp drainage and presumably an independent agricultural tradition in the highlands dates back to beyond 6,000 years ago (Denham et al. 2003).
_{Peter Bellwood: "Agriculture, Languages, And Genes In China And Southeast Asia", (AoA).}

So the even shorter answer would be the generic description of absolutely everything that can be found in the wild in the surroundings and yields anything starchy.

Be it in the tubers, roots, seeds, stems, foliage when identified as nourishing and only halfway productive in early forms of cultivation was cultivated. This the spread in all directions until soil and climate limits, which were then slowly expanded by breeding.

One thing should be quite clear: never has any staple food completely replaced another staple food where conditions to grow them are suitable. The relative importance of a single food crop compared to others might change over time. Such is the case for the millets, which were the most dominant species cultivated and today seen as "almost forgot". But all historic and prehistoric societies add food staples to their diets and diversify the available palette, increase yields and avoid catastrophic mono-crop failures.

Over several millennia, four main areas of extension of Neolithic agriculture developed from the four principal expanding centers. Neolithic agriculture from the Near Eastern center expanded step by step in every direction, starting 9,000 years ago. By the eighth millennium before the present, it had spread to the whole Near East and the eastern rivers of the Mediterranean. By the sixth and fifth millennia, it had spread to the western rivers of the Mediterranean and, via the Danube Valley, had penetrated into central Europe, then into northwest Europe. During the same time, it expanded toward the east as far as India and toward the south as far as central Africa, bypassing the large equatorial forest. By the fourth and third millennia, it had progressed toward the east, all along the thick band of broad-leaved forest that borders the south of the taiga, as far as the Far East where it came into contact with agriculture of Chinese origin. In Africa, it continued to expand toward the south, up until recent times.

By the ninth millennium before the present, agriculture of Chinese origin, with a base of millet, had hardly occupied more than the middle and lower valley of the Yellow River. By the eighth millennium, after having adopted the cultivation of rice, it extended as far as the Yangzi River, and 6,000 years ago it had spread to Manchuria, Korea, Japan, Central Asia, Southeast Asia, where it combined with agriculture of New Guinean origin, and South Asia (India), where it encountered agriculture of Near Eastern origin.
_{Marcel Mazoyer & Laurence Roudart: "A History of World Agriculture. From the Neolithic Age to the Current Crisis", Earthscan: London, Sterling, 2006.}

Even for the lands connected geographically closer to "rice is China" in South East Asia itself:

From southern China rice and millet had spread further to mainland Southeast Asia by 4,000 years ago. Prior to the arrival of rice, there is evidence for the consumption of starchy foods, such as palm starch, bananas, arrow root, and Job’s Tears, although it is unclear whether any of these were cultivated, as opposed to gathered. Once adopted, rice cultivation probably remained limited for some time, with evidence for population growth, and agricultural impacts on the wider landscape evident in erosional signatures in offshore ocean sediments, only from around 500 BCE.
_{Eleanor Kingwell-Banham & Cameron A. Petrie & Dorian Q. Fuller: "Early Agriculture in South Asia", in: Graeme Barker & Candice Goucher: "The Cambridge World History. Volume I. A World with Agriculture. 12000 BCE – 500 CE", Cambridge University Press: Cambridge New York, 2015. (CWHA)}

Looking at the region of Thailand which lay in the middle of most of the Asiatic zones of cultural exchange and zones of agricultural expansion:

The majority of their samples consisted of millet (Setaria italica), some Panicum sp., and Coix sp. AMS dating of seeds and charcoal at these sites was good, but complicated by issues of disturbance; however, they feel that the chronology indicates use of millets from the late third millennium BCE with no evidence of rice in the foodways at any of these sites until the first millennium BCE. This again seems to indicate that while rice was present and possibly cultivated in the region by the second millennium BCE, it remained a minor component of the diet.
_{Huw Barton: "Early agriculture in Southeast Asia and the Pacific", CWHA.}

That sounds complicated, because it is. To aid in an overview:

Figure 1 The earliest archaeobotanical records of selected domesticated crops in three regions of Eurasia: W (western region: Europe, the Eastern Mediterranean and Asia west of the Caspian Sea); S (southern region: India, Pakistan and Nepal); E (eastern region: China, Japan and Southeast Asia).

In terms of ecological opportunism, a notable feature of the earliest crops that spread across Eurasia is the brevity of their growth cycle and ripening period. Indeed, the order in which their range expanded relates inversely to the length of their growth cycle. The fast-maturing broomcorn millet was the first crop to spread across Eurasia, followed by buckwheat, foxtail millet and ultimately the relatively slow-maturing bread wheat. We can infer that the most opportune crops were those that could produce high yield under short-period growing seasons. On the one hand, this would permit optimal use of landscapes experiencing long winters and/or dry summers. On the other hand, it would allow crops to be inserted into multiple cropping systems in intensely farmed landscapes.
_{Martin Jones et al.: "Food Globalisation in Prehistory", World Archaeology, 43:4, 665-675, DOI: 10.1080/00438243.2011.624764}

For Asia:

_{Figure 1 The spread of wheat and barley across Asia, with sites representing the earliest finds for each region shown. For a selection of sites with adequate data, the relative proportions of cereals (wheat, barley, rice, broomcorn millet, foxtail millet, and other millets) are shown in the pie graphs.
Sites key: 1. Anau; 2. Gonur; 3. Shahr-i-Sokhta; 4. Mundigak; 5. Shortugai; 6. MiriQalat; 7. Mehrgarh; 8. Pirak; 9. Tarakai Qila; 10. Ghalegay; 11. Kanishpur; 12. Burzahom; 13. Semthan; 14. Harappa; 15. Kunal; 16. Mitathal; 17. Chanudaro; 18. Kanmer; 19. Rojdi; 20. Balathal; 21. Mahagara; 22. Lahuradewa; 23. Senuwar; 24. Chirand; 25. Kayatha; 26. Navdatoli; 27. Nevasa; 28. Apegaon and Paithan; 29. Tuljapur Garhi; 30. Adam Cave; 31. Daimabad; 32. Inamgaon; 33. Piklihal; 34. Hallur; 35. Sanganakallu; 36. Hanumantaraopeta; 37. Mebrak cave; 38. Begash; 39. Qunbake; 40. Yanghai; 41. Gumugou; 42. Xiaohe; 43. Lanzhouwanzi; 44. Huoshaogou; 45.Donghuishan; 46. Fengtai; 47. Xishanping; 48. Zhouyuan; 49. Zhaojialai; 50. Baligang; 51. Zaojiaoshu; 52. Tianposhuiku; 53. Dugangsi; 54. Wangchengang; 55. Liangchengzhen; 56. Zhaojiazhuang; 57. Nam River.}

_{Crop movements between major agricultural centres in Africa and Eurasia discussed in this paper.
Nicole Boivin et al.: "Old World globalization and the Columbian exchange", World Archaeology Vol. 44(3): 452–469 Debates in World Archaeology, 2012. (DOI)}

Only focusing on rice again reveals again that agriculture was invented several times in different places, and first the idea spread from there, then the crops, and millet being the most important of these at first. Notice the very SouthEastern influence of vegeculture from Newguinea and Indonesia:

_{Some hypotheses linking the distribution of subsistence cultures and language affiliation for ca. 3000 BC, with indication of the dispersal directions for north Chinese millets, middle Yangtze rice and millet systems, and possible Dawenkou-related coastal dispersal southwards (Tanshishan and Nanguanli). The basemap is from Fuller et al. (2011b) and shows in grey a reconstruction of land area under wet rice cultivation as a percentage of modern wet rice land area (the percentage scale is indicated in the shaded bar at the right). It is presumed that wet rice supported denser and expanding human populations. Language family abbreviations: AA Austroasiatic, AN Austronesian, P.Drav. Proto- Dravidian, ST Sino-Tibetan.}

_{Some hypotheses linking the distribution of subsistence cul- tures and language affiliation for ca. 2000 BC. Indicated are the crop dispersal towards Southeast Asia and the diffusion of western crops into Longshan China, and Chinese crops, notable millets westwards and southwards (to South Asia, Yemen, Sudan). The basemap is from Fuller et al. (2011b) and shows in grey a reconstruction of land area under wet rice cultivation as a percentage of modern wet rice land area (the percentage scale is indicated in the shaded bar at the right). It is preseumed that wet rice supported denser and expanding human pop- ulations. The Bactria–Margiana Archaeological Complex (BMAC) is indicated. Language family abbreviations: AA Austroasiatic, AN Austronesian, ST Sino-Tibetan. Munda languages are included in the Austroasiatic family.}

_{Some hypotheses relating the rise to dominance of regional languages and state formation built on the infilling of Asian landscapes with intensive rice agriculture. The basemap is from Fuller et al. (2011b) and shows in grey a reconstruction of land area under wet rice cultivation as a percentage of modern wet rice land area (the percentage scale is indicated in the shaded bar at the right). AN Austronesian languages.
Dorian Q. Fuller: "Pathways to Asian Civilizations: Tracing the Origins and Spread of Rice and Rice Cultures", Rice (2011) 4:78–92, (DOI)}

I am not going to even come close to answering this simple question. But it's worth a try because of perennial confusion on Southeast Asia. The region, concept and people of Southeast Asia is, to me, a living museum.

Southeast Asia Political Border

Source: Geographic guide. Country names in orange box, region is the larger dark blue box.

MSEA (mainland SEA), west to east: Burma (Myanmar), Malaysia, Thailand, Laos, Camboadia, Vietnam

ISEA (island SEA), west to east: Indonesia, Malaysia, Singapore, Brunei, Philippines

Is there a straightforward answer?

This question is almost impossible to answer not because of how OP has framed the question. Yes, there are mistakes in the question itself (and I'll get to it below); the question itself is wonderfully simple but impossible to answer because of the diversity of this region.

What is Southeast Asia?

The dynamism and complexity of Southeast Asia (SEA), even to this very day (December 2018) is bewildering:

• 
  ethnic complexity. Scholars and some SEA governments have yet to figure out how to classify their own natives/indigenous groups.


• 
  linguistic. There are 5 (established) language classifications in SEA, but linguistic scholars recently discovered a new language, "Jedek", in 2018! (ScienceAlert).


• 
  physical geography. Historians and anthropolgist separate SEA into mainland and insular regions in their research. In reality the actual communities ignores this separation between islands or the landmass of Asia i.e. mainland SEA. The pattern (of living/communities) is actually based on coastal vs interior (insular region, tropical jungle) as well lowland against upland/highland (mainland region, altitude). Again, this is happening to this very moment. See Zomia, the region within SEA and Against the Grain: A Deep History of the Earliest States (2017) by James C. Scott, a specialist in political science and anthropology of SEA.


• 
  political border of SEA (thankfully, border disputes today are almost non-existent in SEA but here's the catch, is Malaysia part of mainland SEA or is it insular SEA? Answer: It is both - peninsular Malaysia is clearly part of the mainland, but eastern Malaysia is northern half of Borneo, Asia' largest island.

Staple Food for Whom?

Regardless of the agricultural revolution, before or after rice cultivation was introduced to the region, staple food refers to

... a food that makes up the dominant part of a population’s diet. Food staples are eaten regularly—even daily—and supply a major proportion of a person’s energy and nutritional needs. Food staples vary from place to place, depending on the food sources available. ... Most food staples are inexpensive, plant-based foods. They are usually full of calories for energy. Cereal grains and tubers are the most common food staples.

Source: National Geographic

So, just because rice has been introduced, it does not mean it is the main source of food. The natives in some parts of SEA (interior and upland) can and do take other forms of staple food. Even today, look up "swidden culture" in SEA, mainly for SEA upland inhabitants.

Nowadays, staple food in SEA is rice -- with a qualifier, we are speaking mainly of lowland areas of mainland SEA and coastal areas of insular SEA (see point on physical geography, above).

In prehistory, there was no SEA, and they were separated by altitude (lowland vs upland/highland, ethnic prestige goes to inhabitants of the former) and tropical jungle (coastal vs interior, and again, ethnic prestige goes to to inhabitants of the former). Pre-modern polities & states within the last 1,500 years were created in these "superior" spaces (as opposed to the interior and upland regions), e.g. Sukhothai kingdom, Champa polities, Srivijaya city-state, Malacca sultanate, etc.

Thus, given the qualifiers as explained, we could say the staple food of this region (SEA) in prehistory were:

• plant-based: palm-sugar (e.g. sago), bananas, tubes (e.g. taro and yam)


• protein: fish & maritime-based (for insular, coastal; for mainland, riverine)

This is clearly too broad and overly-generalised, yet to be any more precise, the research (question) has to be narrowed to the boundaries of physical geography (not so much political borders).

Ethnobiology

(Or, what we think we know about this region, their lifestyle and foodways.)

Ethnobiology is the study of "the way living things are treated or used by different human cultures. It studies the dynamic relationships between people, biota, and environments, from the distant past to the immediate present".

Jared Diamond made the mistake of believing his scientific education and brilliant mind could anticipate & avert food poisoning. The New Guineans put him in his place!

"I patiently explained to my Fore companions that I read about some mushrooms being poisonous, that I had heard of even expert American mushroom collectors dying because of the difficulty of distinguishing safe from dangerous mushrooms, and that although we are all hungry, it just wasn't worth the risk. At that point my companions got angry and told me to shut up and listen while they explained some things to me. After I had been quizzing them for years about names for hundreds of trees and birds, how could I insult them by assuming they didn't have names for different mushrooms? ... This one, the tanti (mushroom), grew on trees, and it was delicious and perfectly edible."

Guns, Germs and Steel (Vintage, 2005), pg. 144.

He gets no sympathy from me because I experience this same telling off almost every other week.

Full Disclosure: Currently, I live amongst descendants of Malayo-Polynesian speakers, in Malaysia. Just yesterday, not half-hour before I first read this question on HSE, an Indonesian girl living in Malaysia told me about 2 potted plants I bought earlier: "Kita orang kampung buang ini!" (We, villagers / native folks throw such plants away!). Implication of her statement: these plants grows in the wild locally. Like I said, this region is a living museum, endlessly fascinating and much to learn.

Answers will vary depending on specific regions, cultures, and time period; many peoples would have been hunter-gatherers rather than farming anything. Millet is an ancient crop in east Asia and may have predated rice in some areas. In coastal communities, fish and shellfish were a major source of food. Animals were hunted (e.g. deer, antelopes, wild pigs, and smaller animals) and later raised (e.g. cows, pigs). Gathering nuts, fruit, and other vegetables was also common. In the Indian subcontinent, cultivation of cereals such as wheat spread from the middle east.

The Hoabinhian culture of northern Vietnam (until c. 2000 BCE) probably domesticated legumes, as well as eating seafood, meat, nuts, fruit, and other plants. Other cultures in Vietnam were largely hunter-gatherers such as the Đa Bút culture (c. 5000-1000 BCE). The Dapenkeng culture in Taiwan appear to have initially been largely hunter-gatherers, eating a lot of shellfish and fish, before later cultivating rice and millet.

It's a little vague from the question what region you're interested in, as you mention many countries. In Myanmar, people seem to have gone from hunting to rice cultivation (Prehistory of Myanmar). Further west, the Indus Valley Civilisation in what is now Pakistan farmed domesticated wheat and barley before rice.