The use of substitutes in football is often assumed to have begun in the 1950s. This is not the case however. Recently, carrying out some investigations into the career of Italy's  Renzo De Vecchi,  I was surprised to note that his international debut was made as a substitute in 1910. This prompted me to look for other instances of substitutes being used in international matches in the period before the 1914-18 war. 
We will make an important distinction here; a substitute could be one who deputises for an absent player. In this case though, we will look at players who replaced teammates during the course of a match.
In 1908 at the Olympics one of the 2 France teams made a number of line up changes just before kick off (the 9-0 defeat to Denmark 19.10.08) - and this is not included here.
The records from this era still show plenty of examples of subs not being used, players staying on the field as virtual passengers, teams playing on a man short etc.

The timings are taken from IFFHS. 

1. Wales v Scotland (Wrexham,15.04.89)
Alf Pugh replaced by Sam Gillam (30 mins)
The first instance of  a substitute being used occurred in this British Home Championship match. The initial problem was that Wales' selected goalkeeper, Jim Trainer of Preston North End, did not turn up. Some sources state that Preston would not release him for the game. I do not know what their reason for this would be as the league season had ended and the FA Cup final had already taken place. Trainer's absence was only apparent immediately prior to kick off. There was a delay as Wales sought a replacement. Sam Gillam was the man they sent for. Gillam was then on the books of Wrexham, having previously played for Bolton Wanderers. He wasn't at the Racecourse Ground that day though. However, the man he had replaced as Wrexham Olympic's goalkeeper a few seasons earlier was. Allen 'Alf' Pugh was a 20 year old amateur who had returned to play for his local club , Rhostyllen Victoria (Rhostyllen was a village of a few hundred people).
The Scots consented to Wales starting the game with Pugh in goal until Gillam arrived. 
Pugh enjoyed twenty odd minutes of international football before Gillam replaced him. They shared a clean sheet in the first goalless international match for 17 years. 

2. Netherlands v Belgium (
 Rotterdam, 26.04.08)
Charles Cambier replaced by Georges Mathot (half time) or according to some sources
Georges Mathot replaced by Camille Vanhoorden (half time).
The Netherlands captain,  Karel Heijting, approved the replacement. Having looked at various statistics on Belgian international appearances, I believe that it was a case of Georges Mathot coming on for Cambier.

3. Netherlands v  France (Rotterdam, 10. 05.08)
Julien Denis replaced by Victor Denis (55 mins)
A debut for Victor Denis as he came on on place of his brother Julien.  There was, it appears, an element of subterfuge here. Juliien having agreed to feign injury in order to give his brother his debut. Neither brother played another international. Julien was killed in action in 1915, and Calais' stadium is named in his honour. 

Gustav Bark

4. England (Amateurs) v  Switzerland (Royal Park, London, 09.04.10 )
Emile Glaser replaced by Gustav Bark (8 mins)
Emile Glaser was captaining Switzerland for the first time in his 3rd international appearance. In the 8th minute he sustained an injury. He never played international football again. Heinrich Müller took over the captaincy and Gustav Bark came on to make his international debut.  The England Amateur XI were already 1-0 when Glaser left the field, and conceded a further 3 in the next 5 minutes. Centre half  Bark, later a great success in Germany with 1 FC Nuremberg, was reportedly chaired from the field at the end of the game by the England players for his gutsy display. 

Peco Bauwens

5. Germany v Belgium (Duisburg, 16.05.10, )
 Peco Bauwens replaced by Andreas Breynk (55 mins)
Germany (uncharacteristically?) were somewhat disorganized going into this fixture. The National Championship final between Karlsruher FV and FV Holstein Kiel  had been played the previous day. That left only 7 of the German first XI available. Local players were hastily recruited. Andreas Breynk was there as a specatator, but when Peco Bauwens was forced to retire through injury Breynk found himself representing Germany. 
Herr Bauwens, of course, went on to become a leading referee.

Renzo De Vecchi

6. Hungary v Italy (Millenáris Budapest, 26.05.10, )
Aldo Cevenini replaced by Renzo De Vecchi (half time)
Hungary were 2-0 up when the 16 year old defender Renzo De Vecchi came on in place of centre forward Cevenini. Milan's  De Vecchi remains Italy's youngest ever internationalist.

7. England (Amateurs) v Denmark (Park Royal, London,21.10.11)

Sofus Hansen replaced by Ivar-Lykke Seidelin-Nielsen (half time)
Goalkeeper Hansen broke his ankle.  Ivar-Lykke Seidelin-Nielsen came on for the second half and Castella went in goal. 

Henri Leroy

8. Netherlands v Belgium  (Dordrecht, 28.04.12 )
Henri Leroy replaced by Camille Vanhoorden (28 mins)
Another goalkeeper injury. Belgium had already been reduced to 10 men by an injury to Jan Van Cant
Sylvain Brébart went in goal. It must have been quite some game- Belgium fought back from 3-0 down (2 goals in the first 2 minutes!) and had a penalty saved before Netherlands secured a 4-3 win.

9. Finland v Italy (Traneberg Stockholm, 29.06.12 )
Carlo De Marchi replaced by Vittorio Morelli di Popolo (half time)
In the 1912 Olympic tournament substitutes were allowed by mutual agreement. This was the only occasion in which the substitute was called on. In 35 degrees of heat Finland required extra time to beat Italy. These  75 minutes as  a substitute were Morelli di Popolo's only international experience, which is more than the man he replaced, as De Marchi was not called upon again. 

Joseph Musch

10.England (Amateurs)  v Belgium  (County Ground, Swindon, 09.11.12)
Hector Goetinck replaced by Joseph Musch (30 mins)

11. France v  Italy (Stade de Paris, 12.01.13)
Attilio Treré replaced by Carlo Galletti (half time)
Treré damaged his knee in a 'collision'. 

12. England (Amateurs) v Netherlands (Anlaby Road, Hull, 15.11.13)
Jan Vos replaced by Willy van Holthe (half time)
England captain Viv Woodward was a gentleman and a good sport. Not the sort of chap you'd want to collide with , though. When Jan Vos did just that Woodward was so concerned by the ensuing injury that he invited the Dutch to bring on a sub.

Attilio Treré

13. Italy v  Austria (Milan, 11. 01.14)
Guido Ara replaced by Attilio Treré (6 mins)
A year after being substituted Treré was now the substitute, winning his 5th and final cap.