It should be easy to buy air tickets in Bangkok for the trip to Saigon (and Hanoi to BKK), and then to buy tickets in Saigon for the trip to Hanoi, ect., as you have said.
You can also find a local travel agency (here in Taiwan) that specializes on those routes such as Thailand and Vietnam, to arrange air tickets for you. Some big and specialized enough local agencies have subsidiaries in those target cities in Southern Asia and they may offer air tickets in a slightly better fare. I booked my ticket from Siem Reap to Phnom Penh (one-way ticket) through a Taiwanese-owned agency (subsidiary in Phnom Penh) that I got the information (phone number, air fare) about beforehand in Taiwan. But unless you can pick up the ticket in the airport or figure out another easy alternative, it may be a bit inconvenient for you to look for the subsidiary’s address in a city unfamiliar to you. But you can ask your Taiwanese travel agency about this beforehand too.
Also, if you don’t pay up for the tickets of all legs in Taiwan before you leave, make sure you inquire about the fare for each leg first, because sometimes those subsidiaries may try to charge you more than the fare the agency in Taiwan has told you.
But probably in the end, you may prefer to save all the hassle and just to pay a bit more. You’re not going to travel in the shoestring, are you?!!