Gaming . . . Laptop . . . Budget . . . Ouch.
You might try something like the MSI CX61 0NF-257 from Xotic PC. It's probably their cheapest 15.6" 1080p laptop with an actual video card coming in at $699.
You may also want to take a look at some of the new AMD on board video if you are really on a budget and set your expectation accordingly. Sure, they are great on boards, but still on boards none the less.
Keep in mind it's incredibly difficult to fit performance inside a laptop and still keep costs as low as you require.