I am guessing you mean the same gateway device when you say same gateway ? (i.e. you don't mean the same gateway address).
Anyhow, if the gateway has another interface, you can setup a new IP Subnet and give the other interface a GW address for that network.
What Gateway is it. I know that a WatchGuard firewall has a great feature that allows you to add additional Secondary Network IP's to an interface which would then allow you to have two Gateway addresses (for different ip subnets) on a single interface.
Another way would be to add a router to add an additional IP Subnet and route the traffic through to your gateway instead of using the same gateway device.
Is your current subnet running out of address ? (i.e. is 254 hosts no longer enough) Is this why you need a new subnet ? Another option would be to re-address your current subnet using a 255.255.252.0 subnet giving 1022 address ?