The AVR, like most microcontrollers, uses memory-mapped IO. In a nutshell, this means that a part of the memory space of the microcontroller is reserved for the peripherals. When you change a bit in this area of memory, you're not sending a signal to change a bit of memory, you're sending a signal to change the value of a peripheral.
To understand the details of how this works on your AVR, the Special Function Registers section of AVR-libc (and, more importantly, sfr_defs.h and iom328p.h) are recommended reading.
[Warning: Technical writing ahead, pay close attention] For example, PORTB is defined as _SFR_IO8(0x05) in iom328p.h. In sfr_defs.h, _SFR_IO8(io_addr) is defined as _MMIO_BYTE((io_addr) + __SFR_OFFSET). __SFR_OFFSET is 0x20, the location just after the registers. The space after this address and before RAMSTART (0x100) is used for the peripherals. Going back to our example, _MMIO_BYTE(mem_addr) is defined as (*(volatile uint8_t *)(mem_addr)). Therefore, when you write PORTB, you're really writing *(volatile uint8_t *)(0x25), which defines a byte-wide pointer to the location in memory 0x25. [/Warning]
So, when (in C) you write PORTB |= 0x01, you're really writing the value 1 to the peripheral at byte 0x25, or port B pin 0. If this pin is configured as output (using DDRB, which is at 0x24), PORTB |= 0x01 will cause port B pin 0 to go high. Phew!
So, if you use the assembly instructions (SBI - Set Bit in I/O Register):
sbi 0x24,1 ;Data direction set to output
sbi 0x25,1 ;Set port B pin 0 high
You'll set the pin high.
Of course, use inline assembler with GCC and #include <avr/io.h> to get the conventional names and simplify your task.
Note that all of the peripherals use this scheme, not just the IO pins. Read iom328p.h if you're interested in the locations of other peripherals.
You can use AVRA (AVR Assembler) on Linux to develop your assembly language program on Linux. I'm on Linux and free both as in beer & freedom of use.
Plan to use AVRDUDE (also free - both above contexts) to burn in your object code. I have used it in Linux.
Plan to use another (cheap - free as in opensource) Arduino like as a programmer. I have used one here and documented. In my article, I download a bootloader to a new ATmegaxx, instead you can burn in your own program. I did it all through USB (as you asked).
You definitely can use an USB based Arduino or RBBB+USB cable to program your target Arduino using USB. RBBB is indeed a utility Arduino that I have used in that role.
Overall, to use my solution, you would have to use another programmer or another cheap Arduino like RBBB. I also have reviewed RBBB in my other post.
Another way to program your Arduino with another Arduino.
Programming your Arduino using a third party USB programmer.
Best Answer
The Arduino boards can be programmed in assembly. All you need is an ICSP Cable (In Circuit Serial Programmer) and the AVR toolchain (free from ATMEL) to write to the board. You then get the advantage of on board debugging.
As you suggested, you can just slap an ATMEL chip on a breadboard and go to town.
The kit you referenced looks like a great starting point. You can take the chip right off the board and stick it on your own breadboard (as long as it has correctly regulated power and you account for the clock).
EDIT: Apparently you don't need an ICSP to load assembly programs. See comment below for details.