Normal double battles were introduced in gen 3. However, wild double battles were introduced in gen 4 (when you have a partner) and in gen 5, as long as you have two Pokemon in your party, you can go into the dark grass and have a chance of getting a double battle on your own.
Hope I helped :)